https://www.luogu.com.cn/problem/P3345
虽然带有边权，但是树的重心与未带边权时的重心毫无区别的，因为边权为正时树的重心与边权无关。
证明：
设不带边权时树的重心为\(rt\)
\(S(rt)=\sum_{v} w_{x,v} \times val_v\)
假设转移到\(rt\)其中一个子树的祖先\(v\)时：
\(S(v)=S(rt)-w_{rt,v} \times size_v + w_{rt,v} \times (n-size_v)\)
\(\Delta=(n-size_v \times 2) \times w_{rt,v} \ge 0\)，得证
怎样的点是重心？
除了定义，我们可以得到，满足\(size_u \times 2 \ge n\)的深度最大的点\(u\)为重心
可以通过线段树上二分得到
设\(k\)为原树的根
\[ans=\sum_{v} dis(rt,v) \times val_v \\
=\sum_{v} dis(rt,k) \times val_v + dis(v,k) \times val_v - 2 \times dis(lca_{rt,v},k) \times val_v
\]
\(dis(lca_{rt,v},k) \times val_v\)如何处理？
\[\sum_{v} dis(lca_{rt,v},k) \times val_v=\sum_{u为rt及其祖先,u \ne k} size_u \times w_{u,fa_u}
\]
为什么？我们换一种方式，对于每条边记录其贡献
考虑一下\(rt\)和哪些点的\(lca\)到\(k\)路径会经过\(edge_{u,fa_u}\)，显然就是那些在\(u\)子树内的节点嘛！
\(Code:\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 100005
#define ll long long
using namespace std;
int n,q,x,y,z;
int tot,fr[N],d1[N << 1],d2[N << 1],nxt[N << 1];
int f[N],t[N],sz[N],son[N];
int cnt,eg[N],dfn[N],rdfn[N],dep[N],rdis[N];
ll vals=0,diss=0;
struct node
{
int es,l,r;
ll tag,vs,ms;
node *ls,*rs;
}tr[N << 2],*ct=tr,*rt;
void add(int x,int y,int z)
{
tot++;
d1[tot]=y;
d2[tot]=z;
nxt[tot]=fr[x];
fr[x]=tot;
}
void dfs1(int u)
{
sz[u]=1;
int mx=-1;
for (int i=fr[u];i;i=nxt[i])
{
int v=d1[i];
int cost=d2[i];
if (v==f[u])
continue;
f[v]=u;
eg[v]=cost;
dep[v]=dep[u]+1;
rdis[v]=rdis[u]+cost;
dfs1(v);
sz[u]+=sz[v];
if (sz[v]>mx)
mx=sz[v],son[u]=v;
}
}
void dfs2(int u,int tp)
{
dfn[u]=++cnt;
rdfn[cnt]=u;
t[u]=tp;
if (!son[u])
return;
dfs2(son[u],tp);
for (int i=fr[u];i;i=nxt[i])
{
int v=d1[i];
if (v==f[u] || v==son[u])
continue;
dfs2(v,v);
}
}
void build(node *&p,int l,int r)
{
p=ct++;
p->l=l,p->r=r;
if (l==r)
{
p->es=eg[rdfn[l]];
return;
}
int mid=(l+r) >> 1;
build(p->ls,l,mid);
build(p->rs,mid+1,r);
p->es=p->ls->es+p->rs->es;
}
void push_tag(node *&p,ll z)
{
p->vs+=z*p->es;
p->ms+=z;
p->tag+=z;
}
void push_down(node *&p)
{
push_tag(p->ls,p->tag);
push_tag(p->rs,p->tag);
p->tag=0;
}
void update(node *&p)
{
p->vs=p->ls->vs+p->rs->vs;
p->ms=max(p->ls->ms,p->rs->ms);
}
void modi(node *&p,int x,int y,int z)
{
if (p->l==x && p->r==y)
{
push_tag(p,z);
return;
}
push_down(p);
int mid=(p->l+p->r) >> 1;
if (y<=mid)
modi(p->ls,x,y,z); else
if (x>mid)
modi(p->rs,x,y,z); else
{
modi(p->ls,x,mid,z);
modi(p->rs,mid+1,y,z);
}
update(p);
}
ll calcT(node *&p,int x,int y)
{
if (p->l==x && p->r==y)
return p->vs;
push_down(p);
int mid=(p->l+p->r) >> 1;
if (y<=mid)
return calcT(p->ls,x,y); else
if (x>mid)
return calcT(p->rs,x,y); else
return calcT(p->ls,x,mid)+calcT(p->rs,mid+1,y);
}
void modify(int x,int y)
{
while (x)
{
modi(rt,dfn[t[x]],dfn[x],y);
x=f[t[x]];
}
}
ll query(int x)
{
ll ans=0;
while (x)
{
ans+=calcT(rt,dfn[t[x]],dfn[x]);
x=f[t[x]];
}
return ans;
}
int weight()
{
node *p=rt;
while (p->l!=p->r)
{
push_down(p);
if ((p->rs->ms << 1)>=rt->ms)
p=p->rs; else
p=p->ls;
}
return rdfn[p->l];
}
ll calc(int x)
{
return vals*rdis[x]+diss-query(x)*2;
}
int main()
{
scanf("%d%d",&n,&q);
for (int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
dep[1]=1,rdis[1]=0;
dfs1(1);
dfs2(1,1);
build(rt,1,n);
while (q--)
{
scanf("%d%d",&x,&y);
vals+=y;
diss+=(ll)rdis[x]*y;
modify(x,y);
printf("%lld\n",calc(weight()));
}
return 0;
}