题意：求带权重心，即求一个点 (u) ，使得最小化 (sum_{v}dis(u,v) imes w[v])，输出这个最小值。点权带修，多组询问。
动态点分治。。。
先建出点分树，以下的父子关系均是建立在点分树上的。
(s[u]) 表示子树 (u) 的点权和
(sfa[u]) 表示子树 (u) 对 (fa[u]) 的贡献，即 (sum_{vin subtree(u)} dis(v,fa[u]) imes w[v])
(sdis[u]) 表示 (sum_{vin son(u)} sfa[v])
然后维护即可。
#include<iostream>
#include<cstdio>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=100010,Inf=0x3f3f3f3f;
int n,m,num,sum,rt,RT; bool vis[N];
int dfn[N],son[N],d[N],sz[N],mx[N],top[N],pre[N],fa[N];
ll s[N],sdis[N],sfa[N],dis[N];
struct G {
int vr[N<<1],nxt[N<<1],fir[N],w[N<<1],cnt;
inline void add(int u,int v,int ww)
{vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,w[cnt]=ww;}
}e,pe;
inline void dfs(int u) { sz[u]=1;
for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
if(sz[v]) continue; pre[v]=u,d[v]=d[u]+1,dis[v]=dis[u]+e.w[i];
dfs(v); sz[u]+=sz[v]; if(sz[son[u]]<sz[v]) son[u]=v;
}
}
inline void dfs2(int u,int tp) {
dfn[u]=++num,top[u]=tp;
if(son[u]) dfs2(son[u],tp);
for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
if(dfn[v]) continue; dfs2(v,v);
}
}
inline int lca(int u,int v) {
while(top[u]!=top[v]) d[top[u]]>d[top[v]]?u=pre[top[u]]:v=pre[top[v]];
return d[u]<d[v]?u:v;
}
inline ll dist(int u,int v) {return dis[u]+dis[v]-2*dis[lca(u,v)];}
inline void getrt(int u,int fa) {
sz[u]=1,mx[u]=0;
for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
if(vis[v]||v==fa) continue;
getrt(v,u); sz[u]+=sz[v];
mx[u]=max(mx[u],sz[v]);
} mx[u]=max(mx[u],sum-sz[u]);
if(mx[u]<mx[rt]) rt=u;
}
inline void Pre(int u) {
vis[u]=true;
for(R i=e.fir[u];i;i=e.nxt[i]) { R v=e.vr[i];
if(vis[v]) continue;
sum=sz[v],rt=0;
getrt(v,u),getrt(rt,0);
pe.add(fa[rt]=u,v,rt);
Pre(rt);
}
}
inline void change(int u,int vl) {
s[u]+=vl;
for(R i=u;fa[i];i=fa[i]) {
R w=dist(u,fa[i]);
s[fa[i]]+=vl;
sdis[fa[i]]+=1ll*w*vl;
sfa[i]+=1ll*vl*w;
}
}
inline ll cal(int u) {
register ll ret=sdis[u];
for(R i=u;fa[i];i=fa[i]) {
R w=dist(u,fa[i]);
ret+=1ll*(s[fa[i]]-s[i])*w;
ret+=sdis[fa[i]]-sfa[i];
} return ret;
}
inline ll query(int u) {
register ll ret=cal(u);
for(R i=pe.fir[u];i;i=pe.nxt[i]) { R v=pe.vr[i];
if(cal(v)<ret) return query(pe.w[i]);
} return ret;
}
inline void main() {
n=g(),m=g(); for(R i=1,u,v,w;i<n;++i)
u=g(),v=g(),w=g(),e.add(u,v,w),e.add(v,u,w);
dfs(1),dfs2(1,1); sum=n,mx[rt]=Inf;
getrt(1,-1),getrt(rt,-1),RT=rt,Pre(rt);
for(R i=1,u,c;i<=m;++i)
u=g(),c=g(),change(u,c),
printf("%lld
",query(RT));
}
} signed main() {Luitaryi::main(); return 0;}
#include<bits/stdc++.h>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
static char B[1<<15],*S=B,*T=B;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
inline int g() { R x=0,f=1;
register char s; while(!isdigit(s=getchar())) f=s=='-'?-1:f;
do x=x*10+(s^48); while(isdigit(s=getchar())); return x*f;
} const int N=100010;
int n,m,num;
ll W,E,dis[N],s[N<<2],sum[N<<2],tg[N<<2];
int vr[N<<1],nxt[N<<1],fir[N],w[N<<1],cnt;
int dfn[N],rw[N],sz[N<<2],son[N],top[N],pre[N],e[N];
inline void add(int u,int v,int ww) {
vr[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,w[cnt]=ww;
vr[++cnt]=u,nxt[cnt]=fir[v],fir[v]=cnt,w[cnt]=ww;
}
inline void dfs(int u) { sz[u]=1;
for(R i=fir[u];i;i=nxt[i]) {
R v=vr[i]; if(sz[v]) continue;
dis[v]=dis[u]+w[i],pre[v]=u;
dfs(v); sz[u]+=sz[v];
if(sz[son[u]]<sz[v]) son[u]=v;
}
}
inline void dfs2(int u,int tp) {
dfn[u]=++num,top[u]=tp,rw[num]=u,e[num]=dis[u]-dis[pre[u]];
if(son[u]) dfs2(son[u],tp);
for(R i=fir[u];i;i=nxt[i]) { R v=vr[i];
if(dfn[v]) continue; dfs2(v,v);
}
}
#define ls (tr<<1)
#define rs (tr<<1|1)
inline void build(int tr,int l,int r) {
if(l==r) return s[tr]=e[l],void(); R md=l+r>>1;
build(ls,l,md),build(rs,md+1,r);
s[tr]=s[ls]+s[rs];
}
#define upd() (sz[tr]=max(sz[ls],sz[rs]),sum[tr]=sum[ls]+sum[rs])
inline void spread(int tr) {
sz[ls]+=tg[tr],sz[rs]+=tg[tr],
sum[ls]+=1ll*s[ls]*tg[tr],sum[rs]+=1ll*s[rs]*tg[tr],
tg[ls]+=tg[tr],tg[rs]+=tg[tr],tg[tr]=0;
}
inline void change(int tr,int l,int r,int LL,int RR,int vl) {
if(LL<=l&&r<=RR) return sz[tr]+=vl,tg[tr]+=vl,sum[tr]+=1ll*vl*s[tr],void();
if(tg[tr]) spread(tr); R md=l+r>>1;
if(LL<=md) change(ls,l,md,LL,RR,vl);
if(RR>md) change(rs,md+1,r,LL,RR,vl); upd();
}
inline ll query(int tr,int l,int r,int LL,int RR) {
if(LL<=l&&r<=RR) return sum[tr];
if(tg[tr]) spread(tr); R md=l+r>>1;
if(LL>md) return query(rs,md+1,r,LL,RR);
if(RR<=md) return query(ls,l,md,LL,RR);
return query(ls,l,md,LL,RR)+query(rs,md+1,r,LL,RR);
}
inline int div() {
R tr=1,l=1,r=n; while(l<r) {
if(tg[tr]) spread(tr); R md=l+r>>1;
((sz[rs]<<1)>=sz[1])?(l=md+1,tr=rs):(r=md,tr=ls);
} return rw[l];
}
inline void Ct(int u,int vl) {
while(top[u]!=1) change(1,1,n,dfn[top[u]],dfn[u],vl),u=pre[top[u]];
change(1,1,n,1,dfn[u],vl);
}
inline ll Qt(int u) { register ll ret=0;
while(top[u]!=1) ret+=query(1,1,n,dfn[top[u]],dfn[u]),u=pre[top[u]];
return ret+query(1,1,n,1,dfn[u]);
}
inline ll cal(int u) {return W+dis[u]*E-2*Qt(u);}
inline void main() {
n=g(),m=g(); for(R i=1,u,v,w;i<n;++i)
u=g(),v=g(),w=g(),add(u,v,w);
dfs(1),dfs2(1,1);
build(1,1,n),memset(sz,0,(n+1)<<2);
for(R i=1,u,w;i<=m;++i)
u=g(),w=g(),E+=w,W+=1ll*dis[u]*w,Ct(u,w),
printf("%lld
",cal(div()));
}
} signed main() {Luitaryi::main(); return 0;}
2019.12.17