点分治 - 洛谷保存站

## 点分治

### [P3806 点分治1](https://www.luogu.com.cn/problem/P3806)  
#### 思路：  
随便指定一个点为根 $rt$，此时对于 $rt$ 来说，树上距离为 $k$ 的路径可以分为 $2$ 种，经过 $rt$ 的和不经过 $rt$ 的。  
对于经过 $rt$ 的路径，可以由两个子节点 $u,v$ 拼接而成 $dis[u]+dis[v]$。  
对于不经过 $rt$ 的路径，那它一定存在于以 $rt$ 为根的某个子树内， 那我们可以找到那个子树，进行第一类操作。  
但是如果树为一条链，那时间复杂度就变成了 $O(n^2)$ 了，所以我们要让递归的层数尽量小，也就是每次找子树的重心作为子树的树根进行查找。

对于 P3806，在遍历树时，我们可以用 $hd$ 记录有哪些长度的路径，$fl[i]$ 记录是否有长度为 $i$ 的路径。然后把询问离线下来，淀粉质的时候统一处理。
 #### code：
 ```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
const int M=1e7+10;
const int INF=0x3f3f3f3f3f3f3f3f;
int n,m;
struct node
{
	int v,w,nxt;
}e[N*2];
int h[N],tot=0;
int q[105];
int ans[110],siz[N];
int rt,mt,sum;
int vis[N];
int cnt;
int hd[N],dis[N],fl[M]; 
int tmp[N];
void add(int x,int y,int z)
{
	e[++tot].v=y;
	e[tot].w=z;
	e[tot].nxt=h[x];
	h[x]=tot;
}
void getrt(int u,int fa)//找重心 
{
	siz[u]=1;
	int mx=0;
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||vis[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];//记录子树大小 
		mx=max(mx,siz[v]);
	}
	mx=max(mx,sum-siz[u]);
	if(mx<mt)//如果mx<1/2的树大小，就一定是重心（性质 
	{
		mt=mx;
		rt=u;
	}
}
void getdis(int u,int fa)//子树到u的距离 
{
	hd[++cnt]=dis[u];//存在长度为dis[u]的路径 
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||vis[v]) continue;
		dis[v]=dis[u]+e[i].w; 
		getdis(v,u);
	}
}
void calc(int u)
{
	int ii=0;
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(vis[v]) continue;
		cnt=0;
		dis[v]=e[i].w;
		getdis(v,u);
		for(int j=1;j<=cnt;++j)
			for(int k=1;k<=m;++k)
				if(q[k]>=hd[j])//若存在hd[j] 
					ans[k]|=fl[q[k]-hd[j]];//找是否存在q[k]-hd[j]可以与hd[j]构成答案 
		for(int j=1;j<=cnt;j++)
		{
			if(hd[j]<M)
			{
				tmp[++ii]=hd[j];//tmp记录有哪些hd[j]进行了修改，这样可以针对tmp数组内的值进行还原，减少复杂度。 
				fl[hd[j]]=1;
			}
		}
	}
	for(int i=1;i<=ii;i++)	fl[tmp[i]]=0;
}
void solve(int u)
{
	vis[u]=fl[0]=1;
	calc(u);
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(!vis[v])
		{
			sum=siz[v];
			mt=INF;
			getrt(v,0);
			solve(rt);
		}
	}
}
int main()
{	
	memset(h,-1,sizeof h);
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	for(int i=1;i<=m;i++)scanf("%d",&q[i]);
	sum=n;//每次树的大小 
	mt=n;
	getrt(1,0); 
	solve(rt);
	for(int i=1;i<=m;i++)
	{
		if(ans[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}
```
#### 注意：
此题的 $k$ 很大，所以需要针对修改过的值进行复原，否则会RE。

------------

### [P2634 [国家集训队] 聪聪可可](https://www.luogu.com.cn/problem/P2634) 
#### 思路：
可以把所有路径长度都转化为 $1,2,0$ ,然后考虑容斥，若 $ans$ 统计树内到根距离为3的倍数的个数，可以发现我们重复统计了子树内距离为3的倍数的，所以再减去就可以了。
#### code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
const int M=1e7+10;
const int INF=0x3f3f3f3f3f3f3f3f;
int n,m;
struct node
{
	int v,w,nxt;
}e[N*2];
int h[N],tot=0;
int q[105];
int ans[110],siz[N];
int rt,mt,sum;
int vis[N],fz;
int cnt;
int hd[N],dis[N],fl[M];
int tmp[N];
void add(int x,int y,int z)
{
	e[++tot].v=y;
	e[tot].w=z;
	e[tot].nxt=h[x];
	h[x]=tot;
}
void getrt(int u,int fa)
{
	siz[u]=1;
	int mx=0;
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||vis[v]) continue;
		getrt(v,u);
		siz[u]+=siz[v];
		mx=max(mx,siz[v]);
	}
	mx=max(mx,sum-siz[u]);
	if(mx<mt)
	{
		mt=mx;
		rt=u;
	}
}
void getdis(int u,int fa)
{
	hd[dis[u]%3]++;
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(v==fa||vis[v]) continue;
		dis[e[i].v]=dis[u]+e[i].w;
		getdis(e[i].v,u);
	}
}
int calc(int u,int v)
{
/*	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(vis[v]) continue;
		cnt=0;
		dis[v]=e[i].w;
		getdis(v,u);*/ 
	hd[0]=hd[1]=hd[2]=0;
	dis[u]=v;
	getdis(u,0);
	return hd[0]*hd[0]+2*hd[1]*hd[2];
//	}
}
void solve(int u)
{
//	cout<<u<<endl;
	vis[u]=fl[0]=1;
	fz+=calc(u,0);
	for(int i=h[u];~i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(!vis[v])
		{
			fz-=calc(v,e[i].w);
			sum=siz[v];
			mt=INF;
			getrt(v,0);
			solve(rt);
		}
	}
}
int gcd(int x,int y)
{
	if(x==0||y==0) return x+y;
	while(x^=y^=x^=y%=x);
	return y;
}
int main()
{	
	memset(h,-1,sizeof h);
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		z%=3;
		add(x,y,z);
		add(y,x,z);
	}
//	for(int i=1;i<=m;i++)scanf("%d",&q[i]);
	sum=n;
	mt=n;
	getrt(1,0);
	solve(rt);
	int gc=gcd(fz,n*n);
	printf("%d/%d\n",fz/gc,n*n/gc);
	return 0;
}
```
---
[Race](https://www.luogu.com.cn/problem/P4149)

---
### 一道模板题：  
输入点数为 $N$ 一棵树,求树上长度恰好为 $K$ 的路径个数。$n\le50000$  $K\le500$  
思路：  
k很小，所以可以用树形DP；也可以用淀粉质统计每个长度有几条路径，和模板几乎一样的做法。

---
### [P4178 Tree](https://www.luogu.com.cn/problem/P4178)
#### 题面：
给定一棵 $n$ 个节点的树，每条边有边权，求出树上两点距离小于等于 $k$ 的点对数量。
#### 思路：
暴力统计肯定要超时，开一个树状数组代替原本 $fl$ 数组，便于统计小于等于 $k$ 的个数。注意，当单独的一条路径长度$\le k$时，也要统计。

正在渲染内容...