题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3924
度数只有20，所以从一个点暴力枚举其出边，就能知道往哪个方向走。
知道方向之后直接走到点分树的那个部分的儿子上，即一下走到了那个方向的重心。这样只会走 log 次。
需要通过点分树上维护的信息实现 log 查询一个点作为根的答案。
可以维护 f [ i ] 表示自己作为重心管辖部分的点 j 的 \( \sum dis( i , j ) * w[ j ] \)， g [ i ] 表示自己管辖的点 j 的 \( \sum dis( pre[ i ] , j ) * w[ j ] \) ，再维护自己管辖的点的 \( \sum w[ j ] \) ，就能查询答案了。每次就是枚举自己点分树上的父亲，用它们的 f 减去它们下一层孩子的 g 加到自己的答案里，再用它们的 w 减去他们下一层孩子的 w 再乘上到自己的距离加到自己的答案里。
不知为什么时限是 100 s ，所以这样就能过了。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=1e5+5,K=20; int n,hd[N],xnt,to[N<<1],nxt[N<<1],ew[N<<1],eto[N<<1]; int dep[N],pre[N][K],dis[N][K],siz[N],mn,rt; bool vis[N]; ll f[N],g[N],w[N];int xt,go[N],nt[N],hed[N]; int rdn() {int ret=0;bool fx=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();}while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();return fx?ret:-ret; } int Mx(int a,int b){return a>b?a:b;} int Mn(int a,int b){return a<b?a:b;} void add(int x,int y,int z){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;ew[xnt]=z;} void addx(int x,int y){go[++xt]=y;nt[xt]=hed[x];hed[x]=xt;} void getrt(int cr,int fa,int s) {siz[cr]=1;int mx=0;for(int i=hd[cr],v;i;i=nxt[i])if(!vis[v=to[i]]&&v!=fa){getrt(v,cr,s);siz[cr]+=siz[v];mx=Mx(mx,siz[v]);}mx=Mx(mx,s-siz[cr]); if(mx<mn)mn=mx,rt=cr; } void dfs(int cr,int fa,int ds) {pre[cr][++dep[cr]]=rt;dis[cr][dep[cr]]=ds;for(int i=hd[cr],v;i;i=nxt[i])if(!vis[v=to[i]]&&v!=fa)dfs(v,cr,ds+ew[i]); } void init(int cr,int s) {vis[cr]=1;dfs(cr,0,0);for(int i=hd[cr],v;i;i=nxt[i])if(!vis[v=to[i]]){int ts=(siz[v]<siz[cr]?siz[v]:s-siz[cr]);mn=N;getrt(v,cr,ts);addx(cr,rt);eto[i]=rt;init(rt,ts);} } void mdfy(int cr,int k) {for(int i=dep[cr],v;i;i--){w[v=pre[cr][i]]+=k;f[v]+=(ll)dis[cr][i]*k;g[v]+=(ll)dis[cr][i-1]*k;} } ll calc(int cr) {ll ret=f[cr];for(int i=dep[cr]-1,x,y;i;i--)ret+=f[x=pre[cr][i]]-g[y=pre[cr][i+1]]+(w[x]-w[y])*dis[cr][i];return ret; } void solve(int cr,ll nw) {ll mn=nw;int bh=0;for(int i=hd[cr];i;i=nxt[i]){ll tmp=calc(to[i]);if(tmp<nw&&tmp<mn)mn=tmp,bh=i;}if(!bh){printf("%lld\n",nw);return;}solve(eto[bh],calc(eto[bh])); } int main() {n=rdn();int Q=rdn();for(int i=1,u,v,k;i<n;i++)u=rdn(),v=rdn(),k=rdn(),add(u,v,k),add(v,u,k);mn=N;getrt(1,0,n);int cr=rt;init(rt,n);int x,k;while(Q--){x=rdn();k=rdn();mdfy(x,k);solve(cr,f[cr]);}return 0; }
