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;
}