植物学家 (HGOI 2019.2.16 T4)

## 题目大意 给出一棵有n个节点的树，每个点有自己的权值，一开始以r为根。 给出m次操作，每次给出x,y。x=1时代表把y旋转为根；x=2时代表，询问y的子树权值和为多少。 ## 数据范围 对于所有的数据，满足1<=a[i]<=100，1<=n,m<=100000，保证数据全部随机生成。 ### 解法 考试的时候听到大家在说什么dfs序啊，倍增啊，甚至还有树链剖分的。。。 根本全都不需要！！！只是一个很简单很简单的换根，可以说比第一题都简单。 时间复杂度为$O(n+m*k)$,k是什么那，做1操作时，时间复杂度是当前点的深度，2操作时是$O(1)$查询，在加上数据随机生成，所以不可能数据是一条链，反复从一头调到另一头这种极端数据，所以完全没问题！ 先扫一遍数，把子树权值和、父亲是谁处理出来，然后换根的时候，影响的只有它的父节点，所以把父亲节点的父亲与子树和换一遍就好了。。。 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,cnt=-1,rt,tot=0; int val[100100],f[100100],sum[100100]; int head[200100],nxt[200100],to[200100]; void addedge(int x,int y) { cnt++; nxt[cnt]=head[x]; head[x]=cnt; to[cnt]=y; } void Calc(int u,int fa) { f[u]=fa;sum[u]=val[u]; for(int i=head[u];i!=-1;i=nxt[i]) { int v=to[i]; if(v==fa) continue; Calc(v,u); sum[u]+=sum[v]; } } void Change(int u) { if(!f[u]) return; Change(f[u]); sum[f[u]]-=sum[u]; sum[u]+=sum[f[u]]; f[f[u]]=u; } int main() { memset(head,-1,sizeof(head)); scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } for(int i=1;i<=n;i++) scanf("%d",&val[i]),tot+=val[i]; scanf("%d",&rt); Calc(rt,0); while(m--) { int x,y; scanf("%d%d",&x,&y); if(x==1) Change(y),f[y]=0; else printf("%d\n",sum[y]); } return 0; } ```