题：https://ac.nowcoder.com/acm/contest/3979/E
题意：题清
分析：对于单单一个点考虑（这里我们用节点1），我们可以o（n）算出其答案，那么考虑换根后的答案是多少
考虑u->v,显然，要是一条路径（s，t）只有同时经过u和v答案才会变，其余路径不会对答案造成影响
设x为lca（s，t）到s的距离，那么这条路径对u的贡献为x(dis(s,t)-x),而对v的贡献为(x-1)(dis(s,t)-(x-1)),展开后我们就可以找到转移后答案变换了+2x-dis(s,t)-1；
dis（s，t）-1为常量，2*x会随着向上走而增加（为等差数列），所以用树上差分来处理
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back const int inf=0x3f3f3f3f; const ll INF=1e18; const int M=3e5+5; ll deep[M],ans[M]; int sz[M],son[M],fa[M],tp[M]; vector<int>g[M]; struct node{ ll p,q; node(ll pp=0,ll qq=0):p(pp),q(qq){} }a[M]; void dfs1(int u,int f){ deep[u]=deep[f]+1,fa[u]=f,sz[u]=1; for(auto v:g[u]){ if(v!=f){ dfs1(v,u); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v; } } } void dfs2(int u,int top){ tp[u]=top; if(son[u]) dfs2(son[u],top); for(auto v:g[u]){ if(v!=fa[u]&&v!=son[u]) dfs2(v,v); } } int LCA(int x,int y){ while(tp[x]!=tp[y]){ if(deep[tp[x]]>deep[tp[y]]) x=fa[tp[x]]; else y=fa[tp[y]]; } return deep[x]>deep[y]?y:x; } void dfs3(int u){ for(auto v:g[u]){ if(v!=fa[u]){ dfs3(v); a[u].p+=a[v].p; a[u].q+=a[v].q; } } a[u].p-=2ll*a[u].q;///等差 } void dfs4(int u,ll now){ ans[u]=now; for(auto v:g[u]){ if(v!=fa[u]) dfs4(v,now-a[v].p); } } int main(){ int n,m; scanf("%d%d",&n,&m); for(int u,v,i=1;i<n;i++){ scanf("%d%d",&u,&v); g[u].pb(v); g[v].pb(u); } dfs1(1,0); dfs2(1,1); ll num=0; while(m--){ int u,v; scanf("%d%d",&u,&v); int lca=LCA(u,v); int dis=deep[u]+deep[v]-2ll*deep[lca]; a[u].p+=(dis+1);///dis+1部分 a[u].q+=1;///x部分 a[lca].p-=(dis+1-2ll*(deep[u]-deep[lca]));///边差分，全减掉 a[lca].q-=1; /// a[v].p+=(dis+1),a[v].q+=1; a[lca].p-=(dis+1-2ll*(deep[v]-deep[lca])),a[lca].q-=1; /// num+=(deep[u]-deep[lca])*(deep[v]-deep[lca]); } dfs3(1); dfs4(1,num); for(int i=1;i<=n;i++) printf("%lld ",ans[i]); return 0; }