【洛谷P3345】【ZJOI2015】—幻想乡战略游戏（动态点分治）

传送门

由于基础的求带权重心都是$O(n)$的
考虑优化，考虑到以$u$为根的树
如果重心在儿子$v$的子树，那么显然以$v$为补给站也肯定会比$u$优
那么我们可以在树上二分，每次看带权重心在哪颗子树暴力跳
多次询问可以点分树来解决二分

考虑具体实现
我们记录一个$dis1$表示点分树中$u$的子树到$u$的贡献
$dis2$表示$u$对点分树的父亲的贡献
再记录一个$sum$表示子孙$dv$的和

那显然每个点就可以通过点分树上$logn$计算答案
修改也可以$logn$跳点分树
求距离可以用$ST表+欧拉序$做到$O(1)$
加一个二分

复杂度$O(nlog^2n)$

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res*f;
}
const int N=100005;
struct Tree{
	int pos[N],adj[N],nxt[N<<1],to[N<<1],val[N<<1];
	ll dis[N];
	int dfn,st[N<<2][22],cnt,lg[N<<2];
	inline void addedge(int u,int v,int w){
		nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,val[cnt]=w;
	}
	void dfs(int u,int fa){
		st[++dfn][0]=dis[u],pos[u]=dfn;
		for(int e=adj[u];e;e=nxt[e]){
			int v=to[e];if(v==fa)continue;
			dis[v]=dis[u]+val[e];
			dfs(v,u),st[++dfn][0]=dis[u];
		}
	}
	inline void init(){
		dfs(1,0);lg[0]=-1;
		for(int i=1;i<N*4;i++)lg[i]=lg[i>>1]+1;
		for(int i=1;(1<<i)<=dfn;i++)
		for(int j=1;j+(1<<i)-1<=dfn;j++)
			st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
	}
	inline ll getdis(int u,int v){
		if(pos[u]>pos[v])swap(u,v);
		int t=lg[pos[v]-pos[u]+1];
		return dis[u]+dis[v]-2*min(st[pos[u]][t],st[pos[v]-(1<<t)+1][t]);
	}
}T;
int vis[N],siz[N],g[N],fa[N],q,n;
ll dis1[N],dis2[N],sum[N];
int adj[N],nxt[N<<1],to[N<<1],son[N<<1],cnt,maxn,rt;
inline void addedge(int u,int v,int rt){
	nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,son[cnt]=rt;
}
void getrt(int u,int f){
	siz[u]=1,g[u]=0;
	for(int e=T.adj[u];e;e=T.nxt[e]){
		int v=T.to[e];if(v==f||vis[v])continue;
		getrt(v,u),siz[u]+=siz[v];
		if(siz[v]>g[u])g[u]=siz[v];
	}
	g[u]=max(g[u],maxn-siz[u]);
	if(g[u]<g[rt])rt=u;
}
void init(int u,int f){
	vis[u]=1,fa[u]=f;
	for(int e=T.adj[u];e;e=T.nxt[e]){
		int v=T.to[e];if(vis[v]||v==f)continue;
		son[0]=maxn=siz[v],getrt(v,rt=0);
		addedge(u,v,rt);
		init(rt,u);
	}
}
inline void update(int u,ll k){
	sum[u]+=k;
	for(int i=u;fa[i];i=fa[i]){
		ll d=T.getdis(fa[i],u);//cout<<"D:"<<d<<'
';
		dis2[i]+=d*k,dis1[fa[i]]+=d*k;
		sum[fa[i]]+=k;
	}
}
inline ll calc(int u){
	ll ans=dis1[u];
	for(int i=u;fa[i];i=fa[i]){
		int d=T.getdis(fa[i],u);
		ans+=dis1[fa[i]]-dis2[i];
		ans+=d*(sum[fa[i]]-sum[i]);
	}
	return ans;
}
ll query(int u){
	ll ans=calc(u);
	for(int e=adj[u];e;e=nxt[e]){
		ll tmp=calc(to[e]);
		if(tmp<ans)return query(son[e]);
	}
	return ans;
}
signed main(){
	n=read(),q=read();
	for(int i=2;i<=n;i++){
		int u=read(),v=read(),w=read();
		T.addedge(u,v,w),T.addedge(v,u,w);
	}T.init();
	g[0]=maxn=n;
	getrt(1,rt=0);
	int pre=rt;
	init(rt,0),rt=pre;
	for(int i=1;i<=q;i++){
		int u=read(),k=read();
		update(u,k),cout<<query(rt)<<'
';
	}
}