题目地址:https://www.acwing.com/problem/content/description/2526/
分析:
- 对于一棵树,树根的改变不会影响树的拓扑结构,所以改变树根不会影响路径的查询和修改
- 改变树根会影响对某棵子树的修改和查询
- 假设当前树根为root需要查询和修改的子树的根节点为u,初始时树根为1
- 如果u == root,即求整棵树的权值和只需要求原树的权值和即可query_tree(1)
- 如果lca(root,u) == u则在原树中u为root 的根节点则在当前以root为根的树中u为根的子树的权值和,为原树中以root为子树的权值和的补集,求补集等价于在原树中,整棵树的权值之和减去u到root的路径中以u的第一个儿子为根的子树的权值之和
- 用find(root,u)找到u到root的路径中u的第一个儿子,则答案为query_tree(1) - query_tree(ind(root,u))
- 如果lca(root,u) != u则换根对以u为根的子树的权值之和没有影响 答案为query_tree(u);
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #define lc u << 1 #define rc u << 1 | 1 using namespace std; typedef long long LL; const int N = 100010; struct Node { int l,r; LL sum,add; }tr[N * 4]; int h[N],w[N],e[N],ne[N],idx; int id[N],nw[N],son[N],top[N],cnt; int fa[18][N],dep[N],sz[N]; int root; int n,m; void add(int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx ++; } void dfs1(int u,int father) { fa[0][u] = father; sz[u] = 1; dep[u] = dep[father] + 1; for(int k = 1;k <= 17;k ++) fa[k][u] = fa[k - 1][fa[k - 1][u]]; for(int i = h[u];~i;i = ne[i]) { int j = e[i]; dfs1(j,u); sz[u] += sz[j]; if(sz[son[u]] < sz[j]) son[u] = j; } } void dfs2(int u,int t) { id[u] = ++cnt,nw[cnt] = w[u],top[u] = t; // cout << u << " "<< id[u] << endl; if(!son[u]) return; dfs2(son[u],t); for(int i = h[u];~i;i = ne[i]) { int j = e[i]; if(son[u] == j) continue; dfs2(j,j); } } int lca(int a,int b) { // cout << dep[a] << " "<< dep[b] << endl; if(dep[a] < dep[b]) swap(a,b); for(int k = 17;k >= 0;k --) if(dep[fa[k][a]] >= dep[b]) a = fa[k][a]; // cout << a << endl; if(a == b) return a; for(int k = 17;k >= 0;k --) if(fa[k][a] != fa[k][b]) { a = fa[k][a]; b = fa[k][b]; } return fa[0][a]; } void pushup(int u) { tr[u].sum = tr[lc].sum + tr[rc].sum; } void pushdown(int u) { if(tr[u].add) { tr[lc].add += tr[u].add; tr[rc].add += tr[u].add; tr[lc].sum += (tr[lc].r - tr[lc].l + 1) * tr[u].add; tr[rc].sum += (tr[rc].r - tr[rc].l + 1) * tr[u].add; tr[u].add = 0; } } void build(int u,int l,int r) { if(l == r) { tr[u] = {l,r,nw[l],0}; // cout << "tr :" << u << " "<< tr[u].sum << endl; return; } tr[u] = {l,r}; int mid = l + r >> 1; build(lc,l,mid); build(rc,mid + 1,r); pushup(u); // cout << "tr :" << u << " "<< tr[u].sum << " "<< l << " "<< r << endl; } void change(int u,int l,int r,int k) { if(tr[u].l >= l && tr[u].r <= r) { tr[u].add += k; tr[u].sum += (LL)k * (tr[u].r - tr[u].l + 1); return; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if(l <= mid) change(lc,l,r,k); if(r > mid) change(rc,l,r,k); pushup(u); } LL query(int u,int l,int r) { if(tr[u].l >= l && tr[u].r <= r) { // cout << tr[u].sum << " "<< tr[u].l << " "<< tr[u].r << endl; return tr[u].sum; } pushdown(u); int mid = tr[u].l + tr[u].r >> 1; LL res = 0; if(l <= mid) res += query(lc,l,r); if(r > mid) res += query(rc,l,r); return res; } void change_tree(int u,int k) { // cout << id[u] << " "<< id[u] + sz[u] - 1 << endl; change(1,id[u],id[u] + sz[u] - 1,k); } void change_path(int u,int v,int k) { while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u,v); change(1,id[top[u]],id[u],k); u = fa[0][top[u]]; } if(dep[u] < dep[v]) swap(u,v); change(1,id[v],id[u],k); } LL query_tree(int u) { return query(1,id[u],id[u] + sz[u] - 1); } LL query_path(int u,int v) { LL res = 0; // cout << top[u] << " " << top[v] << " "<< id[u] << " "<< id[v] << endl; while(top[u] != top[v]) { if(dep[top[u]] < dep[top[v]]) swap(u,v); res += query(1,id[top[u]],id[u]); // cout << id[top[u]] << " "<< id[u] << " "<< res << endl; u = fa[0][top[u]]; } // cout << id[u] <<" "<< id[v] << " "<< res << endl; if(dep[u] < dep[v]) swap(u,v); return res + query(1,id[v],id[u]); } int find(int x,int y) { for(int k = 17;k >= 0;k --) if(dep[fa[k][x]] >= dep[y] + 1) x = fa[k][x]; return x; } int main() { scanf("%d",&n); for(int i = 1;i <= n;i ++) scanf("%d",&w[i]); memset(h,-1,sizeof h); for(int i = 2;i <= n;i ++) { int a; scanf("%d",&a); add(a,i); } root = 1; dfs1(1,0); // for(int i = 1;i <= n;i ++) // { // for(int k = 0;k <= 17;k ++) printf("%d ",fa[k][i]); // cout << endl; // } dfs2(1,1); build(1,1,n); // cout << lca(2,3) << endl; // cout << query_tree(32) << endl; // cout << find(5,4) << endl; scanf("%d",&m); while(m--) { int t,u,v,k; scanf("%d",&t); if(t == 1) { scanf("%d",&u); root = u; }else if(t == 2) { scanf("%d%d%d",&u,&v,&k); // cout << query_path(u,v) << endl; change_path(u,v,k); //cout << id[u] << " "<< id[v] << endl; // cout << query_path(u,v) << endl; }else if(t == 3) { scanf("%d%d",&u,&k); //cout << id[u] << endl; if(root == u) { change_tree(1,k); }else { int anc = lca(root,u); // cout << root << " "<< u << " "<< anc << endl; if(anc == u) { change_tree(1,k); change_tree(find(root,u),-k); }else { change_tree(u,k); } } }else if(t == 4) { scanf("%d%d",&u,&v); // cout << u << " "<< v << endl; printf("%lld\n",query_path(u,v)); }else { scanf("%d",&u); //cout << id[u] << endl; if(u == root) { printf("%lld\n",query_tree(1)); }else { int anc = lca(root,u); // cout << anc << " "<< id[root] << " "<< id[u] << " "<< id[find(root,u)] << endl; if(anc == u) { printf("%lld\n",query_tree(1)-query_tree(find(root,u))); }else { printf("%lld\n",query_tree(u)); } } } } return 0; }