點分治：

點分治的題目基本一樣，都是路徑計數(shù)。

其復(fù)雜度的保證是依靠 $O(n)$ 找重心的，每一次至少將問題規(guī)模減小為原先的$1/2$。

找重心我喜歡$BFS$防止爆棧。

1 int Root(int x){ 2 dfsn[0]=0; 3 q.push(x); fa[x]=0; 4 flag[x]=1; 5 while(!q.empty()){ 6 int x=q.front(); q.pop(); 7 dfsn[++dfsn[0]]=x; 8 for(int i=g[x];i;i=E[i].to) 9 if(!v[p] && !flag[p]){ 10 fa[p]=x; 11 flag[p]=1; 12 q.push(p); 13 } 14 } 15 for(int i=1;i<=dfsn[0];i++){ 16 siz[dfsn[i]]=1; 17 h[dfsn[i]]=0; 18 flag[dfsn[i]]=0; 19 } 20 int root=0; 21 for(int i=dfsn[0];i>=1;i--){ 22 int x=dfsn[i]; 23 if(fa[x]){ 24 siz[fa[x]]+=siz[x]; 25 h[fa[x]]=max(h[fa[x]],siz[x]); 26 } 27 h[x]=max(h[x],dfsn[0]-siz[x]); 28 if(!root || h[x]<h[root]) root=x; 29 } 30 return root; 31 }

?

故總共有 $O(logn)$ 層。

在每一層我們分別對不同的塊（刪點而形成）采用 $O(siz[p])$ 的算法。

主定理 $T(n) = T(n/2) + O(n)$

總體上是 $O(nlogn)$

大體框架如下

1 void DC(int x){ 2 v[x]=1; 3 for(int i=g[x];i;i=E[i].to) 4 if(!v[p]){ 5 // 大體上是f[x]*ft[x]就是 6 // Ans = (之前的子樹的路徑數(shù))*（當前子樹的路徑數(shù)） 7 } 8 // 將標記什么的清空，注意保證復(fù)雜度是O(siz)不是O(n) 9 for(int i=g[x];i;i=E[i].to) 10 if(!v[p]) DC(Root(p)); 11 }

然后對于點分治路徑的統(tǒng)計，通常有dp，數(shù)據(jù)結(jié)構(gòu)，數(shù)論等等的方法。

注意：要記得上面的方法沒有統(tǒng)計以點x為起點的路徑條數(shù)，記得加上。

?

例題：

BZOJ 3697

題意：

給出一棵樹，每一條邊為黑或白，統(tǒng)計滿足條件的路徑數(shù)

1.路徑上黑色和白色的個數(shù)相等

2.路徑上存在一個點使得起點到當前點黑色和白色的個數(shù)相等，此點不能是起點終點。

乍一看是沒有解法的，套用點分治。

問題轉(zhuǎn)化為統(tǒng)計過點x的合法路徑條數(shù)。

套用dp

$f(x,0)$ 表示和為x，無休息站的

$f(x,1)$ 表示和為x，有休息站的

$$ans = f(0,0) * ft(0,0) + \sum_{i=-d}^d {f(i,0) \cdot ft(-i,1) + f(i,1) \cdot?ft(-i,0) + f(i,1)?\cdot?ft(-i,1)} $$

條件2可以轉(zhuǎn)化為在當前點到x的路徑上有點的$dis(p) = dis(now)$

所以注意保證初始化的復(fù)雜度

所以記錄一下當前的最大深度，初始化 $f$ 數(shù)組和 $ft$ 數(shù)組的時候從0循環(huán)到 $max deep$

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 6 #define N 400010 7 #define p E[i].x 8 #define LL long long 9 #define debug(x) cout<<#x<<" = "<<x<<endl; 10 11 /* 12 樹形dp 13 f(x,0) 表示和為x，無休息站的 14 f(x,1) 表示和為x，有休息站的 15 ans = f[0][0] * ft[0][0] + 16 ∑ f[i][0]*ft[-i][1] + f[i][1]*ft[-i][0] + f[i][1]*ft[-i][1] 17 (-d <= i <= d) 18 */ 19 20 using namespace std; 21 22 struct edge{ 23 int x,to,v; 24 }E[N<<1]; 25 26 int n,totE; 27 int g[N],dfsn[N],fa[N],siz[N],h[N]; 28 bool v[N],flag[N]; 29 LL ans; 30 LL f[N][2],ft[N][2]; 31 queue<int> q; 32 33 void ade(int x,int y,int v){ 34 E[++totE]=(edge){y,g[x],v}; g[x]=totE; 35 } 36 37 int Root(int x){ 38 dfsn[0]=0; 39 q.push(x); fa[x]=0; 40 flag[x]=1; 41 while(!q.empty()){ 42 int x=q.front(); q.pop(); 43 dfsn[++dfsn[0]]=x; 44 for(int i=g[x];i;i=E[i].to) 45 if(!v[p] && !flag[p]){ 46 fa[p]=x; 47 flag[p]=1; 48 q.push(p); 49 } 50 } 51 for(int i=1;i<=dfsn[0];i++){ 52 siz[dfsn[i]]=1; 53 h[dfsn[i]]=0; 54 flag[dfsn[i]]=0; 55 } 56 int root=0; 57 for(int i=dfsn[0];i>=1;i--){ 58 int x=dfsn[i]; 59 if(fa[x]){ 60 siz[fa[x]]+=siz[x]; 61 h[fa[x]]=max(h[fa[x]],siz[x]); 62 } 63 h[x]=max(h[x],dfsn[0]-siz[x]); 64 if(!root || h[x]<h[root]) root=x; 65 } 66 return root; 67 } 68 69 int mxdep; 70 int cnt[N],d[N],dis[N]; 71 72 void dfs(int x,int fa){ 73 mxdep=max(mxdep,d[x]); 74 if(cnt[dis[x]]) ft[dis[x]][1]++; 75 else ft[dis[x]][0]++; 76 cnt[dis[x]]++; 77 for(int i=g[x];i;i=E[i].to) 78 if(p!=fa&&!v[p]){ 79 d[p]=d[x]+1; 80 dis[p]=dis[x]+E[i].v; 81 dfs(p,x); 82 } 83 cnt[dis[x]]--; 84 } 85 86 void DC(int x){ 87 v[x]=1; 88 f[n][0]=1; 89 int mx=0; 90 for(int i=g[x];i;i=E[i].to) 91 if(!v[p]){ 92 dis[p]=n+E[i].v; 93 d[p]=mxdep=1; 94 dfs(p,p); 95 mx=max(mx,mxdep); 96 ans+=(f[n][0]-1)*ft[n][0]; 97 for(int j=-mxdep;j<=mxdep;j++){ 98 ans+=ft[n-j][1]*f[n+j][1]+ 99 ft[n-j][0]*f[n+j][1]+ft[n-j][1]*f[n+j][0]; 100 } 101 for(int j=n-mxdep;j<=n+mxdep;j++){ 102 f[j][0]+=ft[j][0]; 103 f[j][1]+=ft[j][1]; 104 ft[j][0]=ft[j][1]=0; 105 } 106 } 107 for(int i=n-mx;i<=n+mx;i++) 108 f[i][0]=f[i][1]=0; 109 for(int i=g[x];i;i=E[i].to) 110 if(!v[p]) DC(Root(p)); 111 } 112 113 114 int main(){ 115 scanf("%d",&n); 116 for(int i=1,x,y;i<n;i++){ 117 int v; 118 scanf("%d%d%d",&x,&y,&v); 119 if(!v) v=-1; 120 ade(x,y,v); ade(y,x,v); 121 } 122 DC(Root(1)); 123 printf("%lld\n",ans); 124 return 0; 125 } View Code

?

然后是HDU 4812

題意：給出一棵樹，每一個點有一個點權(quán)，找到一條點權(quán)乘積為K的路徑，輸出起點和終點，要求字典序最小。

求一下逆元，然后用map記錄前面的所有子樹能夠到達的權(quán)值（乘積）

注意這是點權(quán)，不同于邊權(quán)，所以在處理過點x的路徑的時候要謹慎，我的做法是將路徑拆為 x點 ， 之前子樹中的一條鏈， 當前子樹中的一條鏈。

用map復(fù)雜度多一個log，然而也能過。

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <map> 5 #include <queue> 6 7 #define N 400010 8 #define LL long long 9 #define mod 1000003 10 #define p E[i].x 11 #define INF 0x3f3f3f3f 12 #define ipos map<int,int>::iterator 13 14 using namespace std; 15 16 struct edge{ 17 int x,to; 18 }E[N<<1]; 19 20 map<int,int> ft,f; 21 int n,ansv[2],totE,K; 22 int h[N],g[N],siz[N],a[N],fa[N],dfsn[N],dis[N]; 23 bool v[N],flag[N]; 24 queue<int> q; 25 26 int add(int a,int b){ 27 if(a+b>=mod) return a+b-mod; 28 return a+b; 29 } 30 31 int mul(int a,int b){ 32 return (int)((LL)a*(LL)b%mod); 33 } 34 35 int qpow(int x,int n){ 36 int ans=1; 37 for(;n;n>>=1,x=mul(x,x)) 38 if(n&1) ans=mul(ans,x); 39 return ans; 40 } 41 42 int inv(int x){ 43 return (int)qpow((LL)x,mod-2LL); 44 } 45 46 void ade(int x,int y){ 47 E[++totE]=(edge){y,g[x]}; g[x]=totE; 48 } 49 50 int Root(int x){ 51 dfsn[0]=0; 52 q.push(x); fa[x]=0; 53 flag[x]=1; 54 while(!q.empty()){ 55 int x=q.front(); q.pop(); 56 dfsn[++dfsn[0]]=x; 57 for(int i=g[x];i;i=E[i].to) 58 if(!v[p] && !flag[p]){ 59 fa[p]=x; 60 flag[p]=1; 61 q.push(p); 62 } 63 } 64 for(int i=1;i<=dfsn[0];i++){ 65 siz[dfsn[i]]=1; 66 h[dfsn[i]]=0; 67 flag[dfsn[i]]=0; 68 } 69 int root=0; 70 for(int i=dfsn[0];i>=1;i--){ 71 int x=dfsn[i]; 72 if(fa[x]){ 73 siz[fa[x]]+=siz[x]; 74 h[fa[x]]=max(h[fa[x]],siz[x]); 75 } 76 h[x]=max(h[x],dfsn[0]-siz[x]); 77 if(!root || h[x]<h[root]) root=x; 78 } 79 return root; 80 } 81 82 void bfs(int x){ 83 dfsn[0]=0; 84 q.push(x); flag[x]=1; 85 while(!q.empty()){ 86 int x=q.front(); q.pop(); 87 dfsn[++dfsn[0]]=x; 88 if(!ft.count(dis[x]) || ft[dis[x]]>x) 89 ft[dis[x]]=x; 90 for(int i=g[x];i;i=E[i].to) 91 if(!v[p] && !flag[p]){ 92 flag[p]=1; 93 dis[p]=mul(dis[x],a[p]); 94 q.push(p); 95 } 96 } 97 for(int i=1;i<=dfsn[0];i++) 98 flag[dfsn[i]]=0; 99 } 100 101 void upd(int a,int b){ 102 if(a>b) swap(a,b); 103 if(ansv[0]>a || ansv[0]==a&&ansv[1]>b){ 104 ansv[0]=a; 105 ansv[1]=b; 106 } 107 } 108 109 void DC(int x){ 110 // printf("node : %d\n",x); 111 v[x]=1; 112 f.clear(); 113 f[1]=x; 114 for(int i=g[x];i;i=E[i].to) 115 if(!v[p]){ 116 ft.clear(); 117 dis[p]=a[p]; 118 bfs(p); 119 for(ipos it=ft.begin();it!=ft.end();it++){ 120 int tmp=(*it).first; 121 if(f.count(mul(mul(K,inv(tmp)),inv(a[x])))){ 122 upd(f[mul(mul(K,inv(tmp)),inv(a[x]))], 123 (*it).second); 124 } 125 } 126 for(ipos it=ft.begin();it!=ft.end();it++){ 127 if(!f.count((*it).first)) f[(*it).first]=(*it).second; 128 else f[(*it).first]=min(f[(*it).first],(*it).second); 129 } 130 } 131 for(int i=g[x];i;i=E[i].to) 132 if(!v[p]) DC(Root(p)); 133 } 134 135 int main(){ 136 // freopen("test.in","r",stdin); 137 while(scanf("%d%d",&n,&K)==2){ 138 ansv[0]=ansv[1]=INF; 139 totE=0; 140 for(int i=1;i<=n;i++) g[i]=0; 141 for(int i=1;i<=n;i++) scanf("%d",&a[i]),v[i]=0; 142 for(int i=1,x,y;i<n;i++){ 143 int v; 144 scanf("%d%d",&x,&y); 145 ade(x,y); 146 ade(y,x); 147 } 148 DC(Root(1)); 149 if(ansv[0]==INF) puts("No solution"); 150 else printf("%d %d\n",ansv[0],ansv[1]); 151 } 152 return 0; 153 } View Code

?

最后是 國家集訓隊的 crash的文明世界

題意：

定義：

求所有點的S(i)

很顯然是點分治，斯特林數(shù)是什么，我不會 TAT

記錄$f(i)$表示$\sum {dist(p,x)^i }$，$ft$同理

考慮每一次統(tǒng)計過x的路徑時將過x的路徑的影響加入子樹中的點，同時在最后將$S(i)$加上$f(K)$

坑點就是合并的時候要用一下 二項式展開

$$ S(p) += \sum_{i=0}^K {C(K,i) * f(K-i) * b^i}$$

然后注意要統(tǒng)計全路徑，所以上面的框架不適用（上面的框架對于當前子樹只能統(tǒng)計遍歷過的子樹，而應(yīng)該是統(tǒng)計所有除了當前子樹的權(quán)值和）

然后就可以了，自己歪歪（看不懂題解），一遍AC爽。

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 6 #define N 200010 7 #define mod 10007 8 #define M 310 9 #define p E[i].x 10 11 using namespace std; 12 /* 13 f[j] 之前的 dist(x,p)^j 14 ft[j] 當前的 dist(x,p)^j 15 S[p] += ∑C(K,i) * a^{K-i} * b^i (0<=i<=K) 16 O(lognK) 17 */ 18 19 int n,K,totE; 20 int g[N],f[M],siz[N],h[N],fa[N],dfsn[N],S[N],d[N]; 21 int C[M][M]; 22 bool v[N],flag[N]; 23 queue<int> q; 24 25 int add(int a,int b){ 26 if(a+b>=mod) return a+b-mod; 27 return a+b; 28 } 29 30 int mul(int a,int b){ 31 return a*b%mod; 32 } 33 34 struct edge{ 35 int x,to; 36 }E[N<<1]; 37 38 void ade(int x,int y){ 39 E[++totE]=(edge){y,g[x]}; g[x]=totE; 40 } 41 42 int qpow(int x,int n){ 43 int ans=1; 44 for(;n;n>>=1,x=mul(x,x)) 45 if(n&1) ans=mul(ans,x); 46 return ans; 47 } 48 49 int Root(int x){ 50 dfsn[0]=0; 51 q.push(x); fa[x]=0; 52 flag[x]=1; 53 while(!q.empty()){ 54 int x=q.front(); q.pop(); 55 dfsn[++dfsn[0]]=x; 56 for(int i=g[x];i;i=E[i].to) 57 if(!v[p] && !flag[p]){ 58 fa[p]=x; 59 flag[p]=1; 60 q.push(p); 61 } 62 } 63 for(int i=1;i<=dfsn[0];i++){ 64 siz[dfsn[i]]=1; 65 h[dfsn[i]]=0; 66 flag[dfsn[i]]=0; 67 } 68 int root=0; 69 for(int i=dfsn[0];i>=1;i--){ 70 int x=dfsn[i]; 71 if(fa[x]){ 72 siz[fa[x]]+=siz[x]; 73 h[fa[x]]=max(h[fa[x]],siz[x]); 74 } 75 h[x]=max(h[x],dfsn[0]-siz[x]); 76 if(!root || h[x]<h[root]) root=x; 77 } 78 return root; 79 } 80 81 void bfs(int x){ 82 dfsn[0]=0; d[x]=1; 83 q.push(x); flag[x]=1; 84 while(!q.empty()){ 85 int x=q.front(); q.pop(); 86 dfsn[++dfsn[0]]=x; 87 for(int i=g[x];i;i=E[i].to) 88 if(!v[p] && !flag[p]){ 89 d[p]=d[x]+1; 90 flag[p]=1; 91 q.push(p); 92 } 93 } 94 for(int i=1;i<=dfsn[0];i++){ 95 int tmp=1; 96 for(int j=0;j<=K;j++){ 97 f[j]=add(f[j],tmp); 98 tmp=mul(tmp,d[dfsn[i]]); 99 } 100 flag[dfsn[i]]=0; 101 } 102 } 103 104 int power[M]; 105 106 void solve(int rt){ 107 dfsn[0]=0; d[rt]=1; 108 q.push(rt); flag[rt]=1; 109 while(!q.empty()){ 110 int x=q.front(); q.pop(); 111 dfsn[++dfsn[0]]=x; 112 for(int i=g[x];i;i=E[i].to) 113 if(!v[p] && !flag[p]){ 114 d[p]=d[x]+1; 115 flag[p]=1; 116 q.push(p); 117 } 118 } 119 for(int i=1;i<=dfsn[0];i++){ 120 int tmp=1; 121 for(int j=0;j<=K;j++){ 122 f[j]=(f[j]-tmp+mod)%mod; 123 tmp=mul(tmp,d[dfsn[i]]); 124 } 125 } 126 // printf("son : %d\n",rt); 127 // for(int i=0;i<=K;i++){ 128 // printf("%d%c",f[i],i==K?'\n':' '); 129 // } 130 for(int t=1;t<=dfsn[0];t++){ 131 int x=dfsn[t]; 132 flag[x]=0; 133 power[0]=1; 134 for(int i=1;i<=K;i++) power[i]=mul(power[i-1],d[x]); 135 for(int i=0;i<=K;i++){ 136 // printf("addto %d = %d\n",x,mul(C[K][i], mul(f[K-i],power[i]))); 137 S[x] = add(S[x], mul(C[K][i], mul(f[K-i],power[i]))); 138 } 139 S[x]=add(S[x],power[K]); 140 } 141 // S[x]=add(S[x],power[K]); 142 for(int i=1;i<=dfsn[0];i++){ 143 int tmp=1; 144 for(int j=0;j<=K;j++){ 145 f[j]=add(f[j],tmp); 146 tmp=mul(tmp,d[dfsn[i]]); 147 } 148 } 149 } 150 //S[p] += ∑C(K,i) * a^{K-i} * b^i (0<=i<=K) 151 void DC(int x){ 152 v[x]=1; 153 // printf("node : %d\n",x); 154 // for(int i=1;i<=dfsn[0];i++) 155 // printf("%d%c",dfsn[i],i==dfsn[0]?'\n':' '); 156 for(int i=0;i<=K;i++) f[i]=0; 157 for(int i=g[x];i;i=E[i].to) 158 if(!v[p]) bfs(p); 159 // printf("before\n"); 160 // for(int i=0;i<=K;i++) printf("%d%c",f[i],i==K?'\n':' '); 161 for(int i=g[x];i;i=E[i].to) 162 if(!v[p]) solve(p); 163 S[x]=add(S[x],f[K]); 164 // printf("base = %d\n",f[K]); 165 for(int i=g[x];i;i=E[i].to) 166 if(!v[p]) DC(Root(p)); 167 } 168 169 int main(){ 170 freopen("civilization.in","r",stdin); 171 freopen("civilization.out","w",stdout); 172 scanf("%d%d",&n,&K); 173 C[0][0]=1; 174 for(int i=1;i<=K;i++){ 175 C[i][0]=1; 176 for(int j=1;j<=i;j++) 177 C[i][j]=add(C[i-1][j-1],C[i-1][j]); 178 } 179 int L,now,A,B,Q,tmp; 180 scanf("%d%d%d%d%d",&L,&now,&A,&B,&Q); 181 for(int i=1,x,y;i<n;i++){ 182 now=(now*A+B)%Q; 183 tmp=(i<L)? i:L; 184 x=i-now%tmp; 185 y=i+1; 186 ade(x,y); 187 ade(y,x); 188 } 189 DC(Root(1)); 190 for(int i=1;i<=n;i++){ 191 printf("%d\n",S[i]); 192 } 193 return 0; 194 } View Code

?

總結(jié)完了點分治，NOI必勝。

轉(zhuǎn)載于:https://www.cnblogs.com/lawyer/p/4625351.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的NOI前总结：点分治的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。