动态点分治学习笔记

对于普通的点分治，我们访问的顺序是当前点->子树中的重心然后递归

然后把重心访问路径重建一棵树就可以维护许多信息

性质

点分树有几个显著特点

树高(log n) ，维护信息暴力跳就可以了
点分树上两点的lca一定在原树两点的路径上
点分树的子树是原树的一个联通快，这也是在点分树上进行换根操作的基础。

维护信息

修改时，我们统计出加点对点分树上父亲的影响，查询时，查询此点到根（重心）的点分树上节点计算它所管辖的区域就行了

具体地说，点 ((i)) 维护点分树上点 ((i)) 的子树的信息，并且维护点 ((i)) 的子树到点分树上 ((i)) 的父亲的信息，统计答案时减一下就行了

[ZJOI2015]幻想乡战略游戏

树上点权修改，询问带权重心

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
inline int read(){
	int x=0,pos=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
	for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return pos?x:-x; 
} 
const int N = 200010;
const int K = 21;
int f[N][K],sum,sz[N],mx[N],vis[N],rt,fa[N],n,m;ll sumv[N],dis1[N],dis2[N],dis[N],dep[N];
struct node{
		int v,nex,w;
};
inline int get_lca(int u,int v){
	if(u==v) return u;
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=K-1;i>=0;i--) if(dep[f[u][i]]>=dep[v]) u=f[u][i];
	if(u==v) return u;
	for(int i=K-1;i>=0;i--) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
	return f[u][0];
}
inline int get_dis(int u,int v){
	int lca=get_lca(u,v);return dis[u]+dis[v]-2*dis[lca];
}
struct TREE2{
	node edge[N];
	int head[N],top;
	inline void add(int u,int v,int w){
		edge[++top].v=v;
		edge[top].nex=head[u];
		edge[top].w=w;
		head[u]=top; 
	} 
	inline void insert(int u,int val){
		sumv[u]+=val;
		for(int i=u;fa[i];i=fa[i]){
			int dist=get_dis(u,fa[i]);
			dis1[fa[i]]+=(ll)dist*val;
			dis2[i]+=(ll)dist*val;
			sumv[fa[i]]+=val;
		}
	}
	inline ll calc(int u){
		ll ans=dis1[u];
		for(int i=u;fa[i];i=fa[i]){
			int dist=get_dis(u,fa[i]);
			ans+=dis1[fa[i]]-dis2[i];
			ans+=dist*(sumv[fa[i]]-sumv[i]);
		}
		return ans;
	}
	inline ll query(int u){
		ll ans=calc(u);
		for(int i=head[u];i;i=edge[i].nex){
			ll tmp=calc(edge[i].w); //注意此处w是原树上u的儿子 
			if(tmp<ans) return query(edge[i].v);//分治处理 
		}
		return ans;
	}
}t2;
struct TREE{
	int head[N],top;
	node edge[N];
	inline void add(int u,int v,int w){
		edge[++top].v=v;
		edge[top].nex=head[u];
		edge[top].w=w;
		head[u]=top; 
	} 
	inline void dfs(int now,int pre){
		dep[now]=dep[pre]+1;
		for(int i=head[now];i;i=edge[i].nex){
			int v=edge[i].v;
			if(v==pre) continue;
			dis[v]=dis[now]+edge[i].w;
			dfs(v,now);
			f[v][0]=now;
		}
	}
	inline void init(){
		for(int j=1;j<K;j++){
			for(int i=1;i<=n;i++){
				f[i][j]=f[f[i][j-1]][j-1];
			}
		}
	}
	inline void getrt(int u,int pre){
		sz[u]=1,mx[u]=0;//注意每次都要初始化 
		for(register int i=head[u];i;i=edge[i].nex){
			int v=edge[i].v;
			if(vis[v]||v==pre) 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 work(int u,int pre){
		vis[u]=1;fa[u]=pre;
		for(register int i=head[u];i;i=edge[i].nex){
			int v=edge[i].v;
			if(vis[v]) continue;
			sum=sz[v];mx[0]=sz[v];rt=0;
			getrt(v,0);t2.add(u,rt,v);
			work(rt,u);
		}
	}
}t1;
int main(){
	n=read(),m=read();
	for(register int i=1;i<n;i++){
		int u=read(),v=read(),w=read();
		t1.add(u,v,w);t1.add(v,u,w);
	}
	t1.dfs(1,0);t1.init(); sum=n; mx[0]=n,rt=0;
	t1.getrt(1,0);
	int tmp=rt;t1.work(rt,0);rt=tmp; 
	for(register int i=1;i<=m;i++){
		int u=read(),e=read();t2.insert(u,e);
		printf("%lld
",t2.query(rt));
	} 
	return 0;
}