应用
点分治适合处理大规模的树上路径信息问题。
个人感觉和 (dsu on tree) 有点像
过程
因为是分治所以我们肯定要把一个大问题分解为更小的子问题
以洛谷上的P4178 Tree为例
首先我们选择一个点开始递归，求出其它的点到该点的距离，把得到的结果存在一个数组里
然后把该数组 (sort) 一下，利用双指针求出到该点的距离之和小于等于 (k) 的点对有多少个
然后把该点打个标记，再去找其它的点进行上述操作
找什么样的点对我们的复杂度是有很大影响的
经过证明，每次选择剩余子树的重心是最优的，复杂度为 (nlogn)
再加上排序的一个 (log) 复杂度为 (nlog^2n)
要注意的是这种方法需要容斥减去不合法的方案
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int h[maxn],tot=1,n,k;
struct asd{
int to,nxt,val;
}b[maxn];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int siz[maxn],maxsiz[maxn],totsiz,rt,sta[maxn],tp,ans;
bool vis[maxn];
void getroot(rg int now,rg int lat){
siz[now]=1;
maxsiz[now]=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(vis[u] || u==lat) continue;
getroot(u,now);
siz[now]+=siz[u];
maxsiz[now]=std::max(maxsiz[now],siz[u]);
}
maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]);
if(maxsiz[rt]>maxsiz[now]) rt=now;
}
void dfs(rg int now,rg int lat,rg int w){
sta[++tp]=w;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u!=lat && !vis[u]) dfs(u,now,b[i].val+w);
}
}
int js(rg int now,rg int w){
tp=0;
dfs(now,0,w);
std::sort(sta+1,sta+tp+1);
rg int nans=0;
for(rg int i=1,j=tp;;i++){
while(j && sta[i]+sta[j]>k) j--;
if(i>j) break;
nans+=j-i+1;
}
return nans;
}
void dfs2(rg int now){
ans+=js(now,0);
vis[now]=1;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(!vis[u]){
ans-=js(u,b[i].val);
rt=0;
totsiz=siz[u];
getroot(u,0);
dfs2(rt);
}
}
}
int main(){
memset(h,-1,sizeof(h));
n=read();
rg int aa,bb,cc;
for(rg int i=1;i<n;i++){
aa=read(),bb=read(),cc=read();
ad(aa,bb,cc);
ad(bb,aa,cc);
}
k=read();
maxsiz[0]=0x3f3f3f3f,rt=0,totsiz=n;
getroot(1,0);
dfs2(rt);
printf("%d
",ans-n);
return 0;
}
但是有些题是取最大值最小值的操作，我们就不能容斥解决，要稍微改变一下写法
这样写要特判单独一条边的贡献
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int h[maxn],tot=1,n,k;
struct asd{
int to,nxt,val;
}b[maxn<<1];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].val=cc;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int maxsiz[maxn],siz[maxn],totsiz,rt;
bool vis[maxn];
void getroot(rg int now,rg int lat){
siz[now]=1,maxsiz[now]=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat || vis[u]) continue;
getroot(u,now);
siz[now]+=siz[u];
maxsiz[now]=std::max(maxsiz[now],siz[u]);
}
maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]);
if(maxsiz[rt]>maxsiz[now]) rt=now;
}
int sta1[maxn],sta2[maxn],tp,ans=0x3f3f3f3f,mmin[maxn];
void dfs(rg int now,rg int lat,rg int w1,rg int w2){
if(w1>k) return;
sta1[++tp]=w1;
sta2[tp]=w2;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u!=lat && !vis[u]) dfs(u,now,w1+b[i].val,w2+1);
}
}
void js(rg int now,rg int w){
tp=0,mmin[0]=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(vis[u]) continue;
rg int beg=tp+1;
dfs(u,now,b[i].val,1);
for(rg int j=beg;j<=tp;j++) ans=std::min(ans,mmin[k-sta1[j]]+sta2[j]);
for(rg int j=beg;j<=tp;j++) mmin[sta1[j]]=std::min(mmin[sta1[j]],sta2[j]);
}
for(rg int i=1;i<=tp;i++) mmin[sta1[i]]=0x3f3f3f3f;
}
void dfs2(rg int now){
vis[now]=1;
js(now,0);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(vis[u]) continue;
rt=0,totsiz=siz[u];
getroot(u,0);
dfs2(rt);
}
}
int main(){
memset(mmin,0x3f,sizeof(mmin));
memset(h,-1,sizeof(h));
n=read(),k=read();
rg int aa,bb,cc;
for(rg int i=1;i<n;i++){
aa=read(),bb=read(),cc=read();
aa++,bb++;
ad(aa,bb,cc);
ad(bb,aa,cc);
if(cc==k) ans=1;
}
totsiz=n,rt=0,maxsiz[0]=0x3f3f3f3f;
getroot(1,0);
dfs2(rt);
if(ans==0x3f3f3f3f) ans=-1;
printf("%d
",ans);
return 0;
}
整体上点分治的思想还是比较简单的