先不考虑换根。考虑修改某个点权值对答案的影响。显然这只会改变其祖先的子树权值和，设某祖先原子树权值和为s，修改后权值增加了x，则对答案的影响为(s+x)2-s2=2sx+x2。可以发现只要维护每个点到根的路径的子树和之和就可以了，随便树剖一波。
对于换根，可以发现这也只会改变其祖先的子树权值和。设原本的根到要换的根这段路径上的点子树权值和依次为S、s1、s2……sn，则换根后其依次为S-s1、S-s2……S-sn、S，答案变化量为(S-s1)2-S2+……+S2-sn2=(S-s1)2-s12+(S-s2)2-s22+……+(S-sn)2-sn2=nS2-2S(s1+……+sn)。同样只需要维护每个点到根的路径的子树和之和。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 200010#define ll long longint n,q,p[N],a[N],t,S,cnt=0;int tag[N],top[N],id[N],son[N],fa[N],deep[N],size[N],value[N<<2];int L[N<<2],R[N<<2],lazy[N<<2];ll ans,sum[N<<2];struct data{ int to,nxt;}edge[N<<1];void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}void dfs1(int k){ size[k]=1;value[k]=a[k]; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]) { fa[edge[i].to]=k; deep[edge[i].to]=deep[k]+1; dfs1(edge[i].to); size[k]+=size[edge[i].to]; value[k]+=value[edge[i].to]; if (size[edge[i].to]>size[son[k]]) son[k]=edge[i].to; } ans+=1ll*value[k]*value[k];}void dfs2(int k,int from){ top[k]=from; id[k]=++cnt;tag[cnt]=k; if (son[k]) dfs2(son[k],from); for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=fa[k]&&edge[i].to!=son[k]) dfs2(edge[i].to,edge[i].to);}void up(int k){sum[k]=sum[k<<1]+sum[k<<1|1];}void down(int k){ sum[k<<1]+=1ll*lazy[k]*(R[k<<1]-L[k<<1]+1),sum[k<<1|1]+=1ll*lazy[k]*(R[k<<1|1]-L[k<<1|1]+1); lazy[k<<1]+=lazy[k],lazy[k<<1|1]+=lazy[k]; lazy[k]=0;}void build(int k,int l,int r){ L[k]=l,R[k]=r,lazy[k]=0; if (l==r) {sum[k]=value[tag[l]];return;} int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k);}void add(int k,int l,int r,int x){ if (L[k]==l&&R[k]==r) {sum[k]+=1ll*x*(r-l+1);lazy[k]+=x;return;} if (lazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) add(k<<1,l,r,x); else if (l>mid) add(k<<1|1,l,r,x); else add(k<<1,l,mid,x),add(k<<1|1,mid+1,r,x); up(k);}ll query(int k,int l,int r){ if (L[k]==l&&R[k]==r) return sum[k]; if (lazy[k]) down(k); int mid=L[k]+R[k]>>1; if (r<=mid) return query(k<<1,l,r); else if (l>mid) return query(k<<1|1,l,r); else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);}ll tot(int k){ ll s=0; while (k) { s+=query(1,id[top[k]],id[k]); k=fa[top[k]]; } return s;}void modify(int k,int x){ while (k) { add(1,id[top[k]],id[k],x); k=fa[top[k]]; }}int main(){#ifndef ONLINE_JUDGE freopen("datastructure.in","r",stdin); freopen("datastructure.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),q=read(); for (int i=1;i