洛谷P4689 [Ynoi2016] 这是我自己的发明

zrzring 2021-01-13 PM 118℃ 0条

不弱于树上数颜色,考虑莫队,把树变为序列处理

瓶颈在于换根,换根后,1号点到这个根的路径上的点的子树为“整棵树减去当前根节点到该点路径中离x最近的那个点的子树”

于是树变序列需要将这一段区间的点拆成两部分,加上询问本身就需要拆成4个,询问最多可以达到16个

但是整棵树对应的序列左右端点均固定,可以预处理,这样一来不固定的端点又只剩4个了,和一个简单的询问这题一样拆成4个询问即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10, M = 5e5 + 10;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct EDGE {int u, v, nxt;} edge[N << 1];

struct QRY {int p1, p2, id, type;} qry[M << 2];

int n, m, cur, T, head[N], dat[N], b[N], bel[N], L[N], R[N];

int fst[N], fin[N], fa[N], son[N], opt[M];

long long ans[M], res[N], cnt[N], cnt1[N], cnt2[N];

void add(int u, int v) {edge[++cur] = (EDGE){u, v, head[u]}; head[u] = cur;}

bool cmp(QRY a, QRY b) {
    return bel[a.p1] == bel[b.p1] ? bel[a.p1] & 1 ? a.p2 < b.p2 : a.p2 > b.p2 : a.p1 < b.p1;
}

namespace LCA {
    int cur, fa[N], son[N], top[N], dfn[N], siz[N], dep[N];

    void dfs1(int u, int last) {
        dep[u] = dep[last] + 1; fa[u] = last; siz[u] = 1;
        for (int e = head[u]; e; e = edge[e].nxt) {
            int v = edge[e].v; if (v == last) continue; dfs1(v, u);
            siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v;
        }
    }

    void dfs2(int u, int front) {
        dfn[u] = ++cur; top[u] = front; if (son[u]) dfs2(son[u], front);
        for (int e = head[u]; e; e = edge[e].nxt) {
            int v = edge[e].v; if (v == fa[u] || v == son[u]) continue; dfs2(v, v);
        }
    }

    int find(int x, int y) {
        if (dep[x] > dep[y]) return 0;
        while (top[x] != top[y]) {
            y = top[y]; if (fa[y] == x) return y; y = fa[y]; if (!y || dep[y] < dep[x]) return 0;
        }
        return son[x];
    }
}

void dfs(int u, int last) {
    fst[u] = ++cur; dat[cur] = b[u]; fa[u] = last;
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].v; if (v == last) continue; dfs(v, u);
    }
    fin[u] = cur;
}

void init() {
    int B = n / sqrt(T), C = 0; cur = 0; dfs(1, 0);
    for (int i = 1; i <= N; i += B) {
        L[++C] = i; R[C] = min(i + B - 1, N);
    }
    for (int i = 1; i <= C; i++) {
        for (int j = L[i]; j <= R[i]; j++) bel[j] = i;
    }
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) dat[i] = read(), b[i] = dat[i];
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) dat[i] = lower_bound(b + 1, b + n + 1, dat[i]) - b;
    for (int i = 1; i <= n; i++) b[i] = dat[i], cnt[b[i]]++;
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(); add(u, v); add(v, u);
    }
    int rt = 1; cur = 0; dfs(1, 0); LCA::dfs1(1, 0); LCA::dfs2(1, 1); n = cur; cur = 0;
    for (int i = 1; i <= n; i++) {
        res[i] = res[i - 1] + cnt[dat[i]];
    }
    for (int i = 1; i <= m; i++) {
        opt[i] = read();
        if (opt[i] == 1) rt = read();
        if (opt[i] == 2) {
            int x = read(), y = read(), sx = LCA::find(x, rt), sy = LCA::find(y, rt);
            if (x == rt && y == rt) {ans[i] = res[n]; continue;}
            if (x == rt) {
                if (sy) ans[i] = res[n] - res[fin[sy]] + res[fst[sy] - 1];
                else ans[i] = res[fin[y]] - res[fst[y] - 1]; continue;
            }
            if (y == rt) {
                if (sx) ans[i] = res[n] - res[fin[sx]] + res[fst[sx] - 1];
                else ans[i] = res[fin[x]] - res[fst[x] - 1]; continue;
            }
            if (sx && sy) ans[i] += res[n] - res[fin[sx]] + res[fst[sx] - 1] - res[fin[sy]] + res[fst[sy] - 1];
            else if (sx) ans[i] += res[fin[y]] - res[fst[y] - 1];
            else if (sy) ans[i] += res[fin[x]] - res[fst[x] - 1];
            if ((bool)sx ^ (bool)sy) {
                if (sx) x = sx; if (sy) y = sy;
                qry[++cur] = (QRY){fin[x], fin[y], i, 0};
                qry[++cur] = (QRY){fin[x], fst[y] - 1, i, 1};
                qry[++cur] = (QRY){fst[x] - 1, fin[y], i, 1};
                qry[++cur] = (QRY){fst[x] - 1, fst[y] - 1, i, 0};
            } else {
                if (sx) x = sx; if (sy) y = sy;
                qry[++cur] = (QRY){fin[x], fin[y], i, 1};
                qry[++cur] = (QRY){fin[x], fst[y] - 1, i, 0};
                qry[++cur] = (QRY){fst[x] - 1, fin[y], i, 0};
                qry[++cur] = (QRY){fst[x] - 1, fst[y] - 1, i, 1};
            }
        }
    }
    int p1 = 0, p2 = 0; T = cur; init(); long long res = 0; sort(qry + 1, qry + T + 1, cmp);
    for (int i = 1; i <= T; i++) {
        while (p1 < qry[i].p1) p1++, cnt1[dat[p1]]++, res += cnt2[dat[p1]];
        while (p1 > qry[i].p1) cnt1[dat[p1]]--, res -= cnt2[dat[p1]], p1--;
        while (p2 < qry[i].p2) p2++, cnt2[dat[p2]]++, res += cnt1[dat[p2]];
        while (p2 > qry[i].p2) cnt2[dat[p2]]--, res -= cnt1[dat[p2]], p2--;
        if (qry[i].type) ans[qry[i].id] += res; else ans[qry[i].id] -= res;
    }
    for (int i = 1; i <= m; i++) if (opt[i] == 2) printf("%lld\n", ans[i]);
    return 0;
}
Title - Artist
0:00