點分治學習筆記
應用
點分治適合處理大規模的樹上路徑資訊問題。
個人感覺和 \(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\n",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);
}
totsiz=n,rt=0,maxsiz[0]=0x3f3f3f3f;
getroot(1,0);
dfs2(rt);
if(ans==0x3f3f3f3f) ans=-1;
printf("%d\n",ans);
return 0;
}
整體上點分治的思想還是比較簡單的
