简要题意：

给你一棵树。请你支持两个操作，链上加所有点权值+1，选择一个点并最小化它到所有点的距离乘上那个点的权值之和。

每次修改后回答一次。

保证树的形态随机。

题解：

std是一个需要树的形态随机的垃圾做法，丢掉不管。

我们来考虑树的形态任意怎么做，同时我们把链上加权值的范围放宽到任意正数。

首先发现要求的是带权重心。

链加的时候，一个点作为带权重心的时候的权值可以用树剖+BIT或者直接一个LCT维护。单次询问$O({\log }^{2}n)$或者大常数$O(\log n)$，我们希望找到新的带权重心后只算一次。

注意到带权子树$siz$大于总$siz$一半的点形成一个从根拉下来的路径，并且这条路径上最深的点就是带权重心。

显然新的带权重心一定在1.原重心 2.链加的两个端点，这三个点到根的路径上，二分位置，然后我们需要快速计算现在的子树带权$siz$。

注意到是链加子树求和，差分+dfs序+BIT维护，单次询问$O(\log n)$，然后算上二分的一个$O(\log n)$，这一部分是$O({\log }^{2}n)$。

另外二分之后我们还需要支持查询一个点的k级祖先，可以用轻重链剖分或者倍增做到$O(\log n)$，也可以长剖之后做到$O(1)$，不过没有必要。

然后说修改，修改分为两部分，一部分是对于带权$siz$，另一部分是针对带权重心权值的，第一个是$O(\log n)$，第二个是$O({\log }^{2}n)$。

总复杂度压到两个$\log$。

---

代码：

#include<bits/stdc++.h> #define ll long long #define re register #define cs const namespace IO{ inline char gc(){ static cs int Rlen=1<<22|1; static char buf[Rlen],*p1,*p2; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++; } template<typename T>inline T get(){ char c;T num; while(!isdigit(c=gc()));num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; }inline int gi(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; cs int N=1e5+7; int n,m; int el[N],nxt[N<<1|1],to[N<<1|1],ec; inline void adde(int u,int v){ nxt[++ec]=el[u],el[u]=ec,to[ec]=v; nxt[++ec]=el[v],el[v]=ec,to[ec]=u; } ll tot_v,tot_dv; int G,maxn; int siz[N],son[N],d[N],fa[N]; int top[N],bot[N],in[N],out[N],ps[N],dfn; void dfs1(int u,int p){ fa[u]=p,d[u]=d[p]+1; for(int re e=el[u],v;e;e=nxt[e]) if((v=to[e])!=p){ dfs1(v,u);siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; }++siz[u];tot_v++,tot_dv+=d[u]; int mx=std::max(siz[son[u]],n-siz[u]); if(!G||mx<maxn)maxn=mx,G=u; } void dfs2(int u,int tp){ top[u]=tp,in[u]=++dfn;ps[dfn]=u; if(son[u])dfs2(son[u],tp),bot[u]=bot[son[u]];else bot[u]=u; for(int re e=el[u],v;e;e=nxt[e]) if((v=to[e])!=fa[u]&&v!=son[u]) dfs2(v,v);out[u]=dfn; } inline int jump(int u,int k){ while(k>d[u]-d[top[u]]){ k-=d[u]-d[top[u]]+1; u=fa[top[u]]; } return ps[in[u]-k]; } inline int find_mid(int u,int v,int p){ if(d[u]>d[v])std::swap(u,v); int dis=d[u]+d[v]-2*d[p]; if(dis&1){ v=jump(v,dis>>1); if(in[v]<=in[G]&&in[G]<=out[v])return fa[v]; else return v; }else return jump(v,dis>>1); } inline int LCA(int u,int v){ while(top[u]!=top[v])d[top[u]]<d[top[v]]?v=fa[top[v]]:u=fa[top[u]]; return d[u]<d[v]?u:v; } inline int dis(int u,int v){return d[u]+d[v]-2*d[LCA(u,v)];} struct BIT{ll a[N]; void add(int p,ll v){for(;p<=n;p+=p&-p)a[p]+=v;} void add(int l,int r,ll v){add(l,v);add(r+1,-v);} ll qy(int p){ll r=0;for(;p;p&=p-1)r+=a[p];return r;} ll qy(int l,int r){return qy(r)-qy(l-1);} }t1,t2,t3,t4; inline ll qsz(int u){ static ll tmp[N];static int lst[N]; if(!u||lst[u]==m)return tmp[u]; tmp[u]=t1.qy(in[u],out[u])-t2.qy(in[u],out[u])*d[u]; lst[u]=m;return tmp[u]+=siz[u]; } inline void add_chain(int u,int w){ if(!u)return ; tot_dv+=w*d[u]*(d[u]+1ll)/2;tot_v+=w*d[u]; t1.add(in[u],w*(d[u]+1ll));t2.add(in[u],w); for(int re p=u;p;p=fa[top[p]]){ t3.add(in[p],w*(d[p]-d[top[p]]+1ll)*(d[p]+d[top[p]])/2+w*(d[u]-d[p])*d[p]); if(p!=top[p])t4.add(in[p]-1,w); } } inline void calc_G(int &G,int p){ int l=0,r=d[G]-d[p]; while(l<r){ int m=l+r>>1,v=jump(G,m);ll tot=qsz(v); if(tot*2==tot_v){G=v;return ;} if(tot*2<tot_v){l=m+1;} else r=m; }G=jump(G,l); } inline ll get_val(int G){ ll ans=(ll)d[G]*tot_v+tot_dv;ll tmp=0; for(int re u=G,pre=0;u;pre=top[u],u=fa[top[u]]){ tmp+=t3.qy(in[top[u]],in[u]); tmp+=t4.qy(in[u],in[bot[u]])*(d[u]-d[top[u]]+1ll)*(d[u]+d[top[u]])/2; tmp+=(qsz(son[u])-qsz(pre))*d[u]; }return ans-tmp*2; } inline void update_G(int ed){ int p=LCA(ed,G),G1=ed,G2=G; calc_G(G1,p),calc_G(G2,p); if(d[G1]>=d[G2])cout<<get_val(G1)<<"\n",G=G1; else cout<<get_val(G2)<<"\n",G=G2; } signed main(){ #ifdef zxyoi freopen("scissor.in","r",stdin); #endif n=gi(),m=gi(); for(int re i=1;i<n;++i)adde(gi(),gi()); dfs1(1,0);dfs2(1,1); for(int re i=1;i<=n;++i){ t3.add(in[i],(ll)d[i]*(siz[i]-siz[son[i]])); } while(m--){ int u=gi(),v=gi(); int p=LCA(u,v),c=find_mid(u,v,p); add_chain(u,1),add_chain(v,1); add_chain(p,-1),add_chain(fa[p],-1); update_G(c); } return 0; }