这道题可以说是真的板子题啦
恩一看就想到了树链剖分，于是乎很快码出了代码
Code1：
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define ls x << 1 4 #define rs x << 1 | 1 5 using namespace std; 6 ll read() { 7 ll re = 0, f = 1; 8 char ch = getchar(); 9 while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();} 10 while ('0' <= ch && ch <= '9') {re = re * 10 + ch - '0'; ch = getchar();} 11 return re * f; 12 } 13 const int N = 1e6 + 7; 14 int n, m, r; 15 int tot, head[N]; 16 ll sum[N << 2], lazy[N << 2]; 17 ll Id, w[N], wt[N], id[N], fa[N], top[N], siz[N], son[N], dep[N]; 18 struct node{ 19 int net, to; 20 }e[N * 3]; 21 void add(int u, int v) { 22 e[++tot] = {head[u], v}; 23 head[u] = tot; 24 } 25 void dfs1(int u, ll f, ll deep) { 26 dep[u] = deep; 27 fa[u] = f; 28 siz[u] = 1; 29 int maxson = -1; 30 for (int i = head[u]; i; i = e[i].net) { 31 int to = e[i].to; 32 if (to == f) { 33 continue; 34 } 35 dfs1(to, u, deep + 1); 36 siz[u] += siz[to]; 37 if (siz[to] > maxson) { 38 son[u] = to; 39 maxson = siz[to]; 40 } 41 } 42 } 43 void dfs2(int u, ll topf) { 44 id[u] = ++Id; 45 wt[Id] = w[u]; 46 top[u] = topf; 47 if (!son[u]) { 48 return; 49 } 50 dfs2(son[u], topf); 51 for (int i = head[u]; i; i = e[i].net) { 52 int to = e[i].to; 53 if (to == fa[u] || to == son[u]) { 54 continue; 55 } 56 dfs2(to, to); 57 } 58 } 59 void pushdown(int x, int l, int r) { 60 if (lazy[x]) { 61 int mid = (l + r) / 2; 62 lazy[ls] += lazy[x]; 63 lazy[rs] += lazy[x]; 64 sum[ls] += lazy[x] * (mid - l + 1); 65 sum[rs] += lazy[x] * (r - mid); 66 lazy[x] = 0; 67 } 68 } 69 void build(int x, int l, int r) { 70 if (l == r) { 71 sum[x] = wt[l]; 72 return; 73 } 74 int mid = (l + r) / 2; 75 build(ls, l, mid), build(rs, mid + 1, r); 76 sum[x] = sum[ls] + sum[rs]; 77 } 78 void change(int x, int l, int r, int L, int R, ll v) { 79 if (R < l || r < L) { 80 return; 81 } 82 if (L <= l && r <= R) { 83 lazy[x] += v; 84 sum[x] += v * (r - l + 1); 85 return; 86 } 87 pushdown(x, l, r); 88 int mid = (l + r) / 2; 89 if (L <= mid) { 90 change(ls, l, mid, L, R, v); 91 } 92 if (R > mid) { 93 change(rs, mid + 1, r, L, R, v); 94 } 95 sum[x] = sum[ls] + sum[rs]; 96 } 97 ll query(int x, int l, int r, int L, int R) { 98 if (R < l || r < L) { 99 return 0; 100 } 101 if (L <= l && r <= R) { 102 return sum[x]; 103 } 104 pushdown(x, l, r); 105 ll re = 0; 106 int mid = (l + r) / 2; 107 if (L <= mid) { 108 re += query(ls, l, mid, L, R); 109 } 110 if (R > mid) { 111 re += query(rs, mid + 1, r, L, R); 112 } 113 return re; 114 } 115 void Qchange(int x, int y, ll v) { 116 while (top[x] != top[y]) { 117 if (dep[top[x]] < dep[top[y]]) { 118 swap(x, y); 119 } 120 change(1, 1, n, id[top[x]], id[x], v); 121 x = fa[top[x]]; 122 } 123 if (dep[x] > dep[y]) { 124 swap(x, y); 125 } 126 change(1, 1, n, id[x], id[y], v); 127 } 128 ll Squery(int x) { 129 return query(1, 1, n, id[x], id[x] + siz[x] - 1); 130 } 131 int main () { 132 n = read(), m = read(), r = read(); 133 for (int i = 1; i <= n; i++) { 134 w[i] = read(); 135 } 136 for (int i = 1; i < n; i++) { 137 int u = read(), v = read(); 138 add(u, v), add(v, u); 139 } 140 dfs1(r, 0, 1), dfs2(r, r); 141 build(1, 1, n); 142 while (m--) { 143 int o, x, y, z; 144 o = read(); 145 if (o == 1) { 146 x = read(), y = read(), z = read(); 147 Qchange(x, y, z); 148 } else if (o == 2) { 149 x = read(); 150 printf("%lld ", query(1, 1, n, id[x], id[x])); 151 } else { 152 x = read(); 153 printf("%lld ", Squery(x)); 154 } 155 } 156 return 0; 157 }
正常情况的话就结束了吧
但是！！(毒瘤啊)我们发现T了一个点，于是乎我用尽了各种优化手段，不过都无济于事，想来是算法上该改进一波了，偷瞄了巨佬的代码发现可以用LCA和树状数组维护。大概是开两个数组维护一下，每一个节点的值就是它子树内修改的值的和加上本身
Code2：
1 #include <bits/stdc++.h> 2 #define ll long long 3 #define ls x << 1 4 #define rs x << 1 | 1 5 using namespace std; 6 ll read() { 7 ll re = 0, f = 1; 8 char ch = getchar(); 9 while (ch < '0' || ch > '9') {if (ch == '-') f = -f; ch = getchar();} 10 while ('0' <= ch && ch <= '9') {re = re * 10 + ch - '0'; ch = getchar();} 11 return re * f; 12 } 13 const int N = 1e6 + 7; 14 int n, m, r; 15 int tot, head[N]; 16 int Id, id[N], fa[N], top[N], siz[N], son[N], dep[N]; 17 ll sum[N], w[N], g[N], f[N]; 18 struct node{ 19 int net, to; 20 }e[N * 3]; 21 void add(int u, int v) { 22 e[++tot] = {head[u], v}; 23 head[u] = tot; 24 } 25 void dfs1(int u, ll f, ll deep) { 26 dep[u] = deep; 27 fa[u] = f; 28 siz[u] = 1; 29 int maxson = -1; 30 for (int i = head[u]; i; i = e[i].net) { 31 int to = e[i].to; 32 if (to == f) { 33 continue; 34 } 35 dfs1(to, u, deep + 1); 36 siz[u] += siz[to]; 37 if (siz[to] > maxson) { 38 son[u] = to; 39 maxson = siz[to]; 40 } 41 } 42 } 43 void dfs2(int u, ll topf) { 44 id[u] = ++Id; 45 sum[Id] = w[u]; 46 top[u] = topf; 47 if (!son[u]) { 48 return; 49 } 50 dfs2(son[u], topf); 51 for (int i = head[u]; i; i = e[i].net) { 52 int to = e[i].to; 53 if (to == fa[u] || to == son[u]) { 54 continue; 55 } 56 dfs2(to, to); 57 } 58 } 59 int LCA(int x, int y) {//用树剖求个LCA 60 while (top[x] != top[y]) { 61 if (dep[top[x]] > dep[top[y]]) { 62 x = fa[top[x]]; 63 } else { 64 y = fa[top[y]]; 65 } 66 } 67 return dep[x] < dep[y] ? x : y; 68 } 69 void add(ll *c, int x, ll v) {//注意这里是更新是反向的 70 for (int i = x; i > 0; i -= i & -i) { 71 c[i] += v; 72 } 73 } 74 ll ask(ll *c, ll x) {//查询也是反向的 75 ll re = 0; 76 for (int i = x; i <= n; i += i & -i) { 77 re += c[i]; 78 } 79 return re; 80 } 81 void change(int x, ll v) { 82 add(f, id[x], v); 83 add(g, id[x], v * dep[x]); 84 } 85 ll query(int x) { 86 return ask(g, id[x]) - ask(g, id[x] + siz[x]) - (ask(f, id[x]) - ask(f, id[x] + siz[x])) * (dep[x] - 1); 87 } 88 int main () { 89 n = read(), m = read(), r = read(); 90 for (int i = 1; i <= n; i++) { 91 w[i] = read(); 92 } 93 for (int i = 1; i < n; i++) { 94 int u = read(), v = read(); 95 add(u, v), add(v, u); 96 } 97 dfs1(r, 0, 1), dfs2(r, r); 98 for (int i = n; i >= 1; i--) {//后缀数组 99 sum[i] += sum[i + 1]; 100 } 101 while (m--) { 102 int o, x, y, z; 103 o = read(); 104 if (o == 1) { 105 x = read(), y = read(), z = read(); 106 int lca = LCA(x, y); 107 if (lca != x && lca != y) {//注意修改要讨论两种情况 108 change(x, z); 109 change(y, z); 110 change(lca, -z); 111 change(fa[lca], -z);//lca的位置也要改,所以lca的father以上都要恢复 112 } else { 113 change(fa[lca], -z); 114 change(lca == x ? y : x, z); 115 } 116 } else if (o == 2) { 117 x = read(); 118 printf("%lld ", ask(f, id[x]) - ask(f, id[x] + siz[x]) + w[x]); 119 } else { 120 x = read(); 121 printf("%lld ", query(x) + sum[id[x]] - sum[id[x] + siz[x]]); 122 } 123 } 124 return 0; 125 }