Link

Sol

u1s1 这道题没有修改与 LCA 有关的的话，跟 Luogu3979 遥远的国度 这道题挺像的。众所周知的事情是，换根树剖其实完全不需要“换根”操作，仅仅需要讨论新的根与当前根的关系。

当 $u$ 和 $v$ 在以新根 $root$ 为根的 LCA 为：$LCA(u, root)$, $LCA(v, root)$ 和 $LCA(u, v)$ 中深度最大的一个。根据 $root$ 是否在原来 $u$ 的子树内，我们可以轻易提取出以 $root$ 为根时 $u$ 的子树对应的区间。然后修改对应区间即可。

具体的实现推荐使用树剖，不树剖用倍增也是可以的，但是常数巨大，不开 O2 很难卡过去。

Code

代码略长，但是很好理解

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 3e5 + 5;

int n, q, root, tim, num;
int head[SIZE], dfn[SIZE], bel[SIZE], idx[SIZE], w[SIZE], fa[SIZE], son[SIZE], siz[SIZE], dep[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];

struct seg {
    int l, r, val, tag;
} tree[SIZE << 2];

struct query {
    int opt, u, v, x;
} que[SIZE];

namespace GTR {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (c < 48 || c > 57) b ^= c == '-', c = fetch();
        while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
        return b ? a : -a;
    }
} using GTR::read;

#define lson(p) (p << 1)
#define rson(p) (p << 1 | 1)

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs1(int u, int ff) {
    siz[u] = 1;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == ff) continue;
        fa[v] = u, dep[v] = dep[u] + 1;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs2(int u, int top) {
    dfn[u] = ++ tim, idx[tim] = u, bel[u] = top;
    if (son[u]) dfs2(son[u], top);
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (bel[u] != bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        u = fa[bel[u]];
    }
    return dfn[u] > dfn[v] ? v : u;
}


void pushUp(int p) {
    tree[p].val = tree[lson(p)].val + tree[rson(p)].val;
}

void pushDown(int p) {
    if (tree[p].tag) {
        int len1 = tree[lson(p)].r - tree[lson(p)].l + 1, len2 = tree[rson(p)].r - tree[rson(p)].l + 1;
        tree[lson(p)].val += len1 * tree[p].tag, tree[rson(p)].val += len2 * tree[p].tag;
        tree[lson(p)].tag += tree[p].tag, tree[rson(p)].tag += tree[p].tag;
        tree[p].tag = 0;
    }
}

void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r;
    if (l == r) { tree[p].val = w[idx[l]]; return; }
    int mid = (l + r) >> 1;
    build(lson(p), l, mid), build(rson(p), mid + 1, r);
    pushUp(p);
}    

void modify(int p, int l, int r, int val) {
    if (l <= tree[p].l && tree[p].r <= r) {
        int len = tree[p].r - tree[p].l + 1;
        tree[p].val += len * val, tree[p].tag += val;
        return;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) modify(lson(p), l, r, val);
    if (r > mid) modify(rson(p), l, r, val);
    pushUp(p);
}

int query(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) return tree[p].val;
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
    if (l <= mid) ans += query(lson(p), l, r);
    if (r > mid) ans += query(rson(p), l, r);
    return ans;
}

int find(int u, int v) {
    while (bel[u] != bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        if (fa[bel[u]] != v) u = fa[bel[u]];
        else return bel[u];
    }
    return dfn[u] > dfn[v] ? son[v] : son[u];
}

int ask(int u) {
    if (u == root) return query(1, 1, n);
    else if (dfn[root] < dfn[u] || dfn[root] > dfn[u] + siz[u] - 1) 
        return query(1, dfn[u], dfn[u] + siz[u] - 1);
    else {
        int t = find(root, u);
        return query(1, 1, n) - query(1, dfn[t], dfn[t] + siz[t] - 1);
    }
}

namespace subtask1 {
    void main() {
        for (int i = 1; i <= q; ++ i) {
            if (que[i].opt == 2) {
                int g = lca(que[i].u, que[i].v);
                modify(1, dfn[g], dfn[g] + siz[g] - 1, que[i].x);
            }
            if (que[i].opt == 3) 
                printf("%lld\n", query(1, dfn[que[i].x], dfn[que[i].x] + siz[que[i].x] - 1));
        }    
    }
}

namespace subtask2 {
    void main() {
        for (int i = 1; i <= q; ++ i) {
            if (que[i].opt == 1) root = que[i].x;
            if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
        }    
    }
}

namespace subtask3 {
    void main() {
        for (int i = 1; i <= q; ++ i) {
            if (que[i].opt == 1) root = que[i].x;
            if (que[i].opt == 2) {
                int g = que[i].u;
                modify(1, dfn[g], dfn[g] + siz[g] - 1, que[i].x);
            }
            if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
        }    
    }
}

namespace subtask4 {
    int isSub(int u, int v) { return (dfn[u] >= dfn[v] && dfn[u] <= dfn[v] + siz[v] - 1); }

    void main() {
        for (int i = 1; i <= q; ++ i) {
            if (que[i].opt == 1) root = que[i].x;
            if (que[i].opt == 2) {
                int x = que[i].u, y = que[i].v, g = 0, res1 = isSub(x, root), res2 = isSub(y, root);
                if (res1 && res2) g = lca(x, y);
                else if ((res1 && !res2) || (res2 && !res1)) g = root;
                else {
                    int t1 = lca(x, y), t2 = lca(x, root), t3 = lca(y, root);
                    if (t1 == t2) g = t3; else if (t1 == t3) g = t2; else g = t1;
                }
                if (root == g) modify(1, 1, n, que[i].x);
                else if (dfn[root] < dfn[g] || dfn[root] > dfn[g] + siz[g] - 1)
                    modify(1, dfn[g], dfn[g] + siz[g] - 1, que[i].x);
                else {
                    int t = find(root, g);
                    modify(1, 1, n, que[i].x); modify(1, dfn[t], dfn[t] + siz[t] - 1, -que[i].x);
                }
            }
            if (que[i].opt == 3) printf("%lld\n", ask(que[i].x));
        }
    }
}

signed main() {
    // freopen("tree.in", "r", stdin);
    // freopen("tree.out", "w", stdout);
    n = read(), q = read();
    for (int i = 1; i <= n; ++ i) w[i] = read();
    for (int i = 1, u, v; i < n; ++ i) {
        u = read(), v = read();
        addEdge(u, v); addEdge(v, u);
    }
    root = 1, dep[root] = 1;
    dfs1(root, 0), dfs2(root, root);
    build(1, 1, n);
    int cnt1 = 0, cnt2 = 0, cnt3 = 0, flag = 1;
    for (int i = 1; i <= q; ++ i) {
        que[i].opt = read();
        if (que[i].opt == 1) que[i].x = read(), ++ cnt1;
        if (que[i].opt == 2)
            que[i].u = read(), que[i].v = read(), que[i].x = read(), ++ cnt2, flag &= (que[i].u == que[i].v);
        if (que[i].opt == 3) que[i].x = read(), ++ cnt3;
    }
    subtask4::main();
    return 0;
}