一开始没看懂计算答案的第四部和update2，很迷。然后一直推敲之后才发下我计算的时候漏掉一个关键点。没有把加值的影响放到父节点上。
#include<bits/stdc++.h> #define M ((l + r) / 2) #define ls (rt << 1) #define rs ((rt << 1) | 1) #define UI unsigned int using namespace std; const int maxn = 6e5 + 7; vector<int>Gra[maxn]; UI f[maxn], c[maxn], sz[maxn], w[maxn], sum[maxn << 2], add[maxn], cntSon[maxn], cntSeson[maxn]; int fa[maxn], N, top[maxn], hSon[maxn]; int edn[maxn], stn[maxn]; /** stn dfs序的起点， edn dfs序的终点，hSon 重树，add 加重， cntSon 直接子节点数量 sz 树的总大小， cntSeson 2层子节点的总数量， c 子树重复计算个数， f 未进行操作的子树总值 top 重链的父节点。 **/ ///主要是计算初始值 void dfs1(int u) { cntSeson[u] = cntSon[u] = hSon[u] = c[u] =0; sz[u] = 1; for(auto v: Gra[u]) { if(v == fa[u]) continue; dfs1(v); sz[u] += sz[v]; cntSon[u] ++; cntSeson[u] += cntSon[v] + 1; c[u] += sz[v] * cntSon[v]; if(sz[hSon[u]] < sz[v]) hSon[u] = v; } f[u] = w[u] * (sz[u] + 1); for(auto v: Gra[u]) { if(v == fa[u]) continue; f[u] += (sz[u] - sz[v]) * w[v]; w[u] += w[v]; } } ///dfs序，以及最重要的重树父节点 void dfs2(int u, int t) { top[u] = t; stn[u] = ++N; if(hSon[u]) dfs2(hSon[u], t); for(auto v: Gra[u]) { if(v == fa[u] || hSon[u] == v) continue; dfs2(v, v); } edn[u] = N; } ///查询线段树上的价值 int query(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) return sum[rt]; int ret = 0; if(M >= L) ret += query(L, R, l, M, ls); if(M < R) ret += query(L, R, M + 1, r, rs); return ret; } ///作用之后对父节点的影响 void update1(int x, int val) { while(top[x] != top[1]) { int v = top[x], u = fa[v]; f[u] += (sz[u] - sz[v]) * val; x = u; } } ///存加的价值的影响范围 void update2(int p, UI val, int l, int r, int rt) { sum[rt] += val; if(l == r) return ; if(M >= p) update2(p, val, l, M, ls); else update2(p, val, M + 1, r, rs); } int main() { freopen("data.txt", "r", stdin); int n, m, st, ed; while(~scanf("%d%d", &n, &m)) { memset(add, 0, sizeof(add)); memset(sum, 0, sizeof(sum)); N = 0; for(int i = 1; i <= n; i ++) Gra[i].clear(); for(int i = 2; i <= n; i ++) { scanf("%d", &ed); fa[i] = ed; Gra[ed].push_back(i); Gra[i].push_back(ed); } for(int i = 1; i <= n; i ++) scanf("%u", &w[i]); dfs1(1); dfs2(1, 1); while(m -- ) { int op, u; UI x; scanf("%d", &op); if(op == 1) { scanf("%d%u", &u, &x); add[u] += x; ///沿着重树往上预计算重树点价值的作用，之后就不用重复计算这一部分了，这样重树这里就可以成为一个撬棍 update1(u, x * (1 + cntSeson[u])); ///将每个点的填加的价值放进去线段树 update2(stn[u], x * (cntSeson[u]+ 1), 1, n, 1); } else { scanf("%d", &u); UI ans = f[u]; ///加值时作用在当前节点上的情况 ans += add[u] * (2 + sz[u] * cntSeson[u] - c[u]); if(fa[u])///加值时作用在子节点上的情况 ans += add[fa[u]] * (2 + sz[u] * cntSon[u]); if(fa[fa[u]])///加值时作用在孙子节点上的情况 ans += add[fa[fa[u]]] * (1 + sz[u]); if(hSon[u])///计算除重树内加值的价值，因为已经在update1计算过了到f中了 ans += (sz[u] - sz[hSon[u]]) * query(stn[hSon[u]], edn[hSon[u]], 1, n, 1); printf("%u ",ans); } } } return 0; }