点分治

点分治，是一种针对可带权树上简单路径统计问题的算法。
本质上是一种带优化的暴力，带上一点容斥的感觉。
注意对于树上路径，并不要求这棵树有根，
即我们只需要对无根树进行统计。

找重心

我们先提前算出一共有多少个节点，

然后对于每一个节点，找出它最大的儿子

然后重心就为最大的儿子最小的

代码

void find_root(int now,int last,int tot){
	size[now]=1;
	int bigger=1;
	for(int i=0;i<d[now].size();i++){
		int Next=d[now][i].to;
		if(Next==last||vis[Next])continue;
		find_root(Next,now,tot);
		MAX(bigger,size[Next]);
		size[now]+=size[Next];
	}
	MAX(bigger,tot-size[now]);
	if(bigger<=biggest){
		Root=now;
		biggest=bigger;
	}
	return ;
}

寻找根节点到每一个点的路径

我们使用dis数组记录路径

比较简单，但注意要顺带把size算出来，方便后面求重心

代码

void getDis(int now,int last,int len){
	dis[++st]=len;
	size[now]=1;
	for(int i=0;i<d[now].size();i++){
		int Next=d[now][i].to;
		if(Next==last||vis[Next])continue;
		getDis(Next,now,len+d[now][i].v);
		size[now]+=size[Next];
	}
	return ;
}

例一 [IOI2011]Race

思路

题目要求我们找出一条权值和为k且路径长度最小的路径

方法一

考虑将所有路径，分为经过一个点的路径和不经过该点的路径

我们可以处理出该点到所有点的权值和以及距离

记minn[i]为满足条件的最小的路径长度，path[i]为权值和，cnt[i]为路径数目

我们有转移方程minn[k]=min(minn[k-path[i]]+cnt[i],minn[k]);

这样，我们可以保证答案都是符合条件的

接下来我们分治处理他的子节点

注意：每一次做完一个节点我们要将minn归零

至于我们选取的点，为树的重心，这样他的子树的大小不可能大于size[now]/2

找重心需要O(size)的时间，找点要O(size）时间，转移次数也为O(size)

而最多共有logn层，所以时间复杂度为O(nlogn)

代码1（原来）

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5,maxm=1e6,oo=0x3f3f3f3f;
struct Main_Tree{
	struct node{
		 int size;
	}a[maxn+5];
	struct edge{
		int to,w;
	};
	vector<edge>d[maxn+5];
	bool vis[maxn+5]={false};
	int biggest_child,Root,front,tail,path[maxn],cnt[maxn],n,k,x,y,z,ans=oo;
	int minn[maxm+5];
	void find_root(int now,int fa,int total_size){
		a[now].size=1;
		int biggest=0;
		
		for(int i=0;i<d[now].size();i++){
			int son=d[now][i].to;
			if(son==fa||vis[son])continue;
			find_root(son,now,total_size);
			if(a[son].size>biggest)
				biggest=a[son].size;
			a[now].size+=a[son].size;
		}
		if(total_size-a[now].size>biggest)
			biggest=total_size-a[now].size;
		if(biggest_child>biggest){
			Root=now;
			biggest_child=biggest;		
		}	
		return ;
	}
	void getDis(int now,int fa,int length,int num){
		tail++;
		path[tail]=length;
		cnt[tail]=num;
		a[now].size=1;
//		printf("successful\n");
		for(int i=0;i<d[now].size();i++){
			int son=d[now][i].to;
			if(son==fa||vis[son])continue;
			getDis(son,now,length+d[now][i].w,num+1);
			a[now].size+=a[son].size; 
		}
		return ;
	}
	void calc(int root){
		front=tail=1;
		path[1]=0;
		cnt[1]=0;
		minn[0]=0;
		for(int i=0;i<d[root].size();i++){
			int son=d[root][i].to;
			if(vis[son])continue;
			getDis(son,root,d[root][i].w,1);
			for(int j=front+1;j<=tail;j++)
				if(k-path[j]>=0)
					ans=min(ans,minn[k-path[j]]+cnt[j]);
			for(int j=front+1;j<=tail;j++)
				if(path[j]<=k)
					minn[path[j]]=min(minn[path[j]],cnt[j]);
			front=tail;
		}
//		for(int i=1;i<=k;i++)cout<<minn[i]<<" ";
//		cout<<endl;
		for(int i=1;i<=tail;i++)
			if(path[i]<=k)
				minn[path[i]]=oo;
		vis[root]=true;
		for(int i=0;i<d[root].size();i++){
			int son=d[root][i].to;
			if(vis[son])continue;
			solve(son,root,a[son].size);
		}
		return ;
	}
	void solve(int now,int fa,int total_size){
//		printf("into solve :\n now %d fa %d total_size %d\n",now,fa,total_size);
		Root=now;
		biggest_child=total_size-1;
		find_root(now,fa,total_size);
//		printf("Root is %d \n",Root);
		calc(Root);
		return ;
	}
	void input(){
		memset(minn,0x3f,sizeof minn);
		scanf("%d%d",&n,&k);
		for(int i=1;i<n;i++){
			scanf("%d%d%d",&x,&y,&z);
			x++;
			y++;
			d[x].push_back({y,z});
			d[y].push_back({x,z});
		}
		solve(1,0,n);
		
		if(ans==oo)ans=-1;
		printf("%d",ans);
		
	}
}T;
int main(){
	T.input();

	return 0;
}

代码2（更新后）

#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+5,maxk=1e6+5,oo=1061109567;
int n,k,x,y,z,minn=1e9,cnt[maxk];
struct node{
	int to,v;
};
vector<node>d[maxn];
void MAX(int &a,int b){
	if(a<b)a=b;
	return ;
}
void MIN(int &a,int b){
	if(a>b)a=b;
	return ;
}
struct Main_Tree{
	int Root,biggest,st;
	int size[maxn],dis[maxn],path[maxn];
	bool vis[maxn]={false};
	void find_root(int now,int last,int tot){
		size[now]=1;
		int bigger=1;
		for(int i=0;i<d[now].size();i++){
			int Next=d[now][i].to;
			if(Next==last||vis[Next])continue;
			find_root(Next,now,tot);
			MAX(bigger,size[Next]);
			size[now]+=size[Next];
		}		
		MAX(bigger,tot-size[now]);
		if(bigger<=biggest){
			biggest=bigger;
			Root=now;
		}
		return ;
	}
	void getDis(int now,int last,int len,int NUM){
		dis[++st]=len;
		path[st]=NUM;
		size[now]=1;
		for(int i=0;i<d[now].size();i++){
			int Next=d[now][i].to;
			if(Next==last||vis[Next])continue;
			getDis(Next,now,len+d[now][i].v,NUM+1);
			size[now]+=size[Next];
		}
		return ;
	}
	void calc(int now){
		int sum=0;
		st=0;
		cnt[0]=0;
		for(int i=0;i<d[now].size();i++){
			int Next=d[now][i].to;
			if(vis[Next])continue;
			int L,R;
			L=st+1;
			getDis(Next,now,d[now][i].v,1);
			R=st;
			for(int j=L;j<=R;j++)
				if(k-dis[j]>=0)
					minn=min(minn,cnt[k-dis[j]]+path[j]);
			for(int j=L;j<=R;j++)
				if(dis[j]<=k)
					MIN(cnt[dis[j]],path[j]);
		}
		for(int i=1;i<=st;i++)
			if(dis[i]<=k)
				cnt[dis[i]]=oo;
		return ;
	}
	void solve(int now,int tot){
		biggest=tot-1,Root=now;
		find_root(now,now,tot);
		int rt=Root;
		vis[rt]=true;
		calc(rt);
		for(int i=0;i<d[rt].size();i++){
			int Next=d[rt][i].to;
			if(vis[Next])continue;
			solve(Next,size[Next]);
		}
	}
}Tr;
int main(){
	memset(cnt,0x3f,sizeof cnt);
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		if(x==0)x=n;
		if(y==0)y=n;
		d[x].push_back({y,z});
		d[y].push_back({x,z});
	}
	Tr.solve(1,n);
	if(minn==1e9)minn=-1;
	cout<<minn;

	return 0;
}

例二 P4178 Tree

方法一

实际上我们可以考虑使用容斥原理，我们把从重心出发的路径全部收集到一个数组，

然后减去不合法的方案：来自同一个子树的

注意，我们采用二分进行统计，我们每次只能选两个不同的数

因此我们从这个数的前一位开始找符合条件的数

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=4*1e4+5;
int size[maxn],dis[maxn];
int Root,st=0,ans=0;
int n,k,x,y,z;
struct node{
	int to,v;
};
vector<node>d[maxn]; 
bool vis[maxn]={false};
int biggest;
void MAX(int &a,int b){
	if(b>a)a=b;
	return ;
}
struct Main_Tree{
	void find_root(int now,int last,int tot){
		size[now]=1;
		int bigger=1;
		for(int i=0;i<d[now].size();i++){
			int Next=d[now][i].to;
			if(Next==last||vis[Next])continue;
			find_root(Next,now,tot);
			MAX(bigger,size[Next]);
			size[now]+=size[Next];
		}
		MAX(bigger,tot-size[now]);
		if(bigger<=biggest){
			Root=now;
			biggest=bigger;
		}
		return ;
	}
	void getDis(int now,int last,int len){
		dis[++st]=len;
		size[now]=1;
		for(int i=0;i<d[now].size();i++){
			int Next=d[now][i].to;
			if(Next==last||vis[Next])continue;
			getDis(Next,now,len+d[now][i].v);
			size[now]+=size[Next];
		}
		return ;
	}
	int calc(int now,int tmp){
		int sum=0;
		st=0;
		getDis(now,now,tmp);
		sort(dis+1,dis+st+1); 
		for(int i=st;i>=1;i--){
			int num=max((int)(upper_bound(dis+1,dis+i-1 +1,k-dis[i])-(dis) -1),0);
			sum+=num;
		}
		return sum;
	}
	void solve(int now,int tot){
	
		biggest=tot,Root=now;
		find_root(now,now,tot);
		int rt=Root;

		vis[rt]=true;
		ans+=calc(rt,0);
		for(int i=0;i<d[rt].size();i++){
			int Next=d[rt][i].to;
			if(vis[Next])continue;
			ans-=calc(Next,d[rt][i].v);
			solve(Next,size[Next]);
		}
	}
}Tr;
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&x,&y,&z);
		d[x].push_back({y,z});
		d[y].push_back({x,z});
	}
	scanf("%d",&k);
	Tr.solve(1,n);
	cout<<ans;
	return 0;
}

方法二

该题与上一题不同的是，题目要求我们求权值和小于等于k的路径数目，

我们仅需要在上一题的基础上，使用线段树维护即可

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e4;
struct Tree{
	int a[maxn+5];
	void update(int now,int c){
		now++;
		for(;now<=maxn+1;now+=now&(-now))a[now]+=c;
	}
	int check(int now){
		int ans=0;
		now++;
		for(;now>0;now-=now&(-now))ans+=a[now];
		return ans;
	}
}cnt;
struct Main_Tree{
	struct edge{
		int to,w;
	};
	vector<edge>d[maxn+5];
	int size[maxn+5],path[maxn+5],big_child_size,front,tail,k,ans=0,n,m,x,y,z,root;
	bool vis[maxn+5]={false};
	
	void find_root(int now,int fa,int total_size){
		size[now]=1;
		int big_size=0;
//		printf("now %d fa %d total_size %d successful\n",now,fa,total_size);
		for(int i=0;i<d[now].size();i++){
			int son=d[now][i].to;
			if(son==fa||vis[son])continue;
			find_root(son,now,total_size);
			if(size[son]>big_size)
				big_size=size[son];
			size[now]+=size[son];
		} 
		if(total_size-size[now]>big_size)
			big_size=total_size-size[now];
		if(big_child_size>big_size){
			root=now;
			big_child_size=big_size;
		}
//		cout<<now<<" "<<big_size<<endl;
		return ;
	}
	
	void getDis(int now,int fa,int length){
		path[++tail]=length;
		size[now]=1;
		
		for(int i=0;i<d[now].size();i++){
			int son=d[now][i].to;
			if(son==fa||vis[son])continue;
			getDis(son,now,length+d[now][i].w);
			size[now]+=size[son];
		}
	}
	void calc(int Root){
		front=tail=1;
		path[1]=0;
		cnt.update(0,1);
		vis[Root]=true;
		for(int i=0;i<d[Root].size();i++){
			int son=d[Root][i].to;
			if(vis[son])continue;
			getDis(son,Root,d[Root][i].w);
			for(int j=front+1;j<=tail;j++){
				if(k-path[j]>=0)
					ans+=cnt.check(k-path[j]);
			}
			for(int j=front+1;j<=tail;j++)
				cnt.update(path[j],1);
			front=tail;
		}
		for(int i=1;i<=tail;i++)cnt.update(path[i],-1);
//		for(int i=1;i<=tail;i++)cout<<path[i]<<" ";
//		cout<<endl;
//		for(int i=1;i<=n;i++)cout<<vis[i]<<" ";
//		cout<<endl;
//		for(int i=1;i<=n;i++)cout<<size[i]<<" ";
//		cout<<endl;
		for(int i=0;i<d[Root].size();i++){
			int son=d[Root][i].to;
//			printf("son %d  of %d:\n",son,Root);
			if(vis[son])continue;
			solve(son,Root,size[son]);
		}
		return ;
	}
	void solve(int now,int fa,int total_size){
//		printf("now solve into :%d %d %d \n",now,fa,total_size);	
		root=now;
		big_child_size=total_size-1;
		find_root(now,fa,total_size);
//		printf("root:%d\n",root);
		calc(root);
	}
	
	
	void input(){
		cin>>n;
		for(int i=1;i<=n-1;i++){
			cin>>x>>y>>z;
			d[x].push_back({y,z});
			d[y].push_back({x,z});
		}
		cin>>k;
		solve(1,0,n);
		
		cout<<ans;
		
	}
	
}T;
int main(){
	T.input();

	return 0;
}

例三 P5351 Ruri Loves Maschera

对于这道题，我们就和前几题一样先找重心，然后算出重心距离其他点权值的最大值以及路径长度，

接下来，不同于前面的题，我们对这个数组按权值从小到大排序，我们用树状数组记录路径长度为i的路径数目

在枚举的过程中，我们查询树状数组中[l-path[i],r-path[i]]的路径数目

但这可能出现一个问题，有可能有的答案来自同一个子树，这就不符合要求，于是我们减去同一颗子树的贡献即可

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct Fenwick_Tree{
	int tr[maxn];
	void update(int now,int c){
		for(;now<=1e5;now+=now&(-now))tr[now]+=c;
		return ;
	}
	int check(int now){
		if(now==0)return 0;
		int ans=0;
		for(;now>0;now-=now&(-now))ans+=tr[now];
		return ans;
	}
}T;

struct node{
	int maxx,path;
}a[maxn];
bool cmp(node x,node y){
	if(x.maxx==y.maxx)return x.path<y.path;
	return x.maxx<y.maxx;
}
struct Main_Tree{
	
	struct edge{
		int to,w;
	};
	int n,l,r,x,y,z,biggest,Root,front,tail,ans=0;
	vector<edge>d[maxn];
	int size[maxn];
	bool vis[maxn]={false};
	
	void find_root(int now,int fa,int total){
		size[now]=1;
		int bigger=0;
		for(int i=0;i<d[now].size();i++){
			int son=d[now][i].to;
			if(son==fa||vis[son])continue;
			find_root(son,now,total);
			if(size[son]>bigger)bigger=size[son];
			size[now]+=size[son];
		}
		if(total-size[now]>bigger)bigger=total-size[now];
		if(bigger<biggest){
			Root=now;
			biggest=bigger;
		}
		return ;
	}
	void get_Dis(int now,int fa,int maxx,int length){
		a[++tail]={maxx,length};
		size[now]=1;
		for(int i=0;i<d[now].size();i++){
			int son=d[now][i].to;
			if(son==fa||vis[son])continue;
			get_Dis(son,now,max(maxx,d[now][i].w),length+1);
			size[now]+=size[son];
		}
		return ;
	}
	void calc(int root,int fa,int flag){
		front = 1;
		tail = 0;
		for(int i=0;i<d[root].size();i++){
			int son=d[root][i].to;
			if(root==fa||vis[son])continue;
			get_Dis(son,root,d[root][i].w,1);
		}
//		for(int i=1;i<=tail;i++)cout<<a[i].maxx<<" "<<a[i].path<<endl;
//		cout<<endl;
		sort(a+1,a+tail+1,cmp);
		
		for(int i=1;i<=tail;i++){
			ans+=(T.check(r-a[i].path)-T.check(l-a[i].path-1))*a[i].maxx*flag;
			T.update(a[i].path,1);
		}
		for(int i=1;i<=tail;i++){
			T.update(a[i].path,-1);
		}
		return ;
	}
	void solve(int now,int fa,int total){
//		printf ("now is %d ,fa is %d ,total is %d\n",now,fa,total);
		biggest=total-1;
		Root=now;
		find_root(now,fa,total);
//		printf("Root is %d\n",Root);
		vis[Root]=true;
		calc(Root,0,1);
		for(int i=0;i<d[Root].size();i++){
			int son=d[Root][i].to;
			if(vis[son])continue;
			calc(son,Root,-1);
		}
		int reRoot=Root;
		for(int i=0;i<d[reRoot].size();i++){
			int son=d[reRoot][i].to;
			if(vis[son])continue;
			solve(son,reRoot,size[son]);
		}
	}
	void input(){
		scanf("%d%d%d",&n,&l,&r); 
		for(int i=1;i<n;i++){
			scanf("%d%d%d",&x,&y,&z); 
			d[x].push_back({y,z});
			d[y].push_back({x,z});
		}
		solve(1,0,n);
		cout<<ans*2<<endl;
	}
}Tr;
int main(){
	Tr.input();

	return 0;
}

本栏目推荐文章
• 【C语言】形参和实参的一些注意点
• 汉诺塔问题（分治）
• 一些Mybatis的知识点&易错点总结
• webgl学习02-绘制一个点
• CDQ分治 星之河
• 点一个RGB灯没想到这么多学问 - 基于MicroPython
• 【题解】 P4482 | 后缀自动机 树分治
• wps在win7下提示错误“无法定位程序输入点 ucrtbase.terminate”
• 开篇词｜人人都要会点密码学
• Springboot 扩展点