对于一个点，要求出它到所有点的带权距离和，只需记录下树分治的结构然后查询即可。

修改$O(\log n)$，查询$O(\log n)$。

 

到所有点带权距离和最小的点显然是这棵树的带权重心。

以1号点为根，考虑一条从父亲x到孩子y的边：

若y子树内权值和>=总权值和-y子树内权值和，即2*y子树内权值和>=总权值和，则重心在y的子树里，否则不在。

所以重心一定是深度最大的满足2*子树内权值和>=总权值和的点。

可以发现重心及其祖先都满足2*子树内权值和>=总权值和，而这些点在DFS序上从左往右深度递增。

所以树链剖分后用线段树维护DFS序，修改单点点权相当于一条树链整体加上一个数。

查询重心时直接在线段树上二分即可。

修改$O(\log^2n)$，查询$O(\log n)$。

 

#include
     
      typedef long long ll;const int N=100010,M=2000000,T=262145;int n,m,i,x,y,z;int g[N],nxt[N<<1],v[N<<1],w[N<<1],ok[N<<1],ed=1,son[N],f[N],all,now,cnt,value[N];int size[N],heavy[N],top[N],loc[N],seq[N],dfn;int G[N],NXT[M],V[2][M],W[M],ED,tag[T];ll val[T],sw[N],sdw[N],sew[N],sedw[N];inline void read(int&a){  char c;bool f=0;a=0;  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));  if(c!='-')a=c-'0';else f=1;  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';  if(f)a=-a;}inline void add(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],ok[ed]=1,g[x]=ed;}inline void ADD(int x,int y,int z,int w){V[0][++ED]=y;V[1][ED]=z;W[ED]=w;NXT[ED]=G[x];G[x]=ED;}void findroot(int x,int pre){  son[x]=1;f[x]=0;  for(int i=g[x];i;i=nxt[i])if(ok[i]&&v[i]!=pre){    findroot(v[i],x);    son[x]+=son[v[i]];    if(son[v[i]]>f[x])f[x]=son[v[i]];  }  if(all-son[x]>f[x])f[x]=all-son[x];  if(f[x]
      
       size[heavy[x]])heavy[x]=v[i];  }}void dfs2(int x,int y){  top[x]=y;seq[loc[x]=++dfn]=x;  if(heavy[x])dfs2(heavy[x],y);  for(int i=g[x];i;i=nxt[i])if(v[i]!=heavy[x]&&v[i]!=f[x])dfs2(v[i],v[i]);}inline void add1(int x,int p){val[x]+=p,tag[x]+=p;}inline void pb(int x){if(tag[x])add1(x<<1,tag[x]),add1(x<<1|1,tag[x]),tag[x]=0;}void change(int x,int a,int b,int c,int d,int p){  if(c<=a&&b<=d){add1(x,p);return;}  pb(x);  int mid=(a+b)>>1;  if(c<=mid)change(x<<1,a,mid,c,d,p);  if(d>mid)change(x<<1|1,mid+1,b,c,d,p);  val[x]=val[x<<1]>val[x<<1|1]?val[x<<1]:val[x<<1|1];}inline int getroot(){  int x=1,a=1,b=n,mid;  while(a
       
        >1;    if(val[x<<1|1]*2>=val[1])a=mid+1,x=x<<1|1;else b=mid,x<<=1;  }  return seq[a];}inline void modify(int x,int y){  value[x]+=y;  for(int i=G[x];i;i=NXT[i]){    sw[V[0][i]]+=y,sdw[V[0][i]]+=(ll)W[i]*y;    sew[V[1][i]]+=y,sedw[V[1][i]]+=(ll)W[i]*y;  }  while(top[x]!=1)change(1,1,n,loc[top[x]],loc[x],y),x=f[top[x]];  change(1,1,n,1,loc[x],y);}inline ll query(int x){  ll t=sdw[x];  for(int i=G[x];i;i=NXT[i])t+=(sw[V[0][i]]-sew[V[1][i]]+value[V[0][i]])*W[i]+sdw[V[0][i]]-sedw[V[1][i]];  return t;}int main(){  read(n),read(m);  for(i=1;i