NOI前总结：点分治

点分治：

点分治的题目基本一样，都是路径计数。

其复杂度的保证是依靠 $O(n)$ 找重心的，每一次至少将问题规模减小为原先的$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 = (之前的子树的路径数)*（当前子树的路径数）
 7         }
 8   //    将标记什么的清空，注意保证复杂度是O(siz)不是O(n)
 9     for(int i=g[x];i;i=E[i].to)
10         if(!v[p]) DC(Root(p));
11 }

然后对于点分治路径的统计，通常有dp，数据结构，数论等等的方法。

注意：要记得上面的方法没有统计以点x为起点的路径条数，记得加上。

例题：

BZOJ 3697

题意：

给出一棵树，每一条边为黑或白，统计满足条件的路径数

1.路径上黑色和白色的个数相等

2.路径上存在一个点使得起点到当前点黑色和白色的个数相等，此点不能是起点终点。

乍一看是没有解法的，套用点分治。

问题转化为统计过点x的合法路径条数。

套用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可以转化为在当前点到x的路径上有点的$dis(p) = dis(now)$

所以注意保证初始化的复杂度

所以记录一下当前的最大深度，初始化 $f$ 数组和 $ft$ 数组的时候从0循环到 $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
",ans);
124     return 0;
125 }

View Code

然后是HDU 4812

题意：给出一棵树，每一个点有一个点权，找到一条点权乘积为K的路径，输出起点和终点，要求字典序最小。

求一下逆元，然后用map记录前面的所有子树能够到达的权值（乘积）

注意这是点权，不同于边权，所以在处理过点x的路径的时候要谨慎，我的做法是将路径拆为 x点，之前子树中的一条链，当前子树中的一条链。

用map复杂度多一个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
",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
",ansv[0],ansv[1]);
151     }
152     return 0;
153 }

View Code

最后是国家集训队的 crash的文明世界

题意：

定义：

求所有点的S(i)

很显然是点分治，斯特林数是什么，我不会 TAT

记录$f(i)$表示$sum {dist(p,x)^i }$，$ft$同理

考虑每一次统计过x的路径时将过x的路径的影响加入子树中的点，同时在最后将$S(i)$加上$f(K)$

坑点就是合并的时候要用一下二项式展开

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

然后注意要统计全路径，所以上面的框架不适用（上面的框架对于当前子树只能统计遍历过的子树，而应该是统计所有除了当前子树的权值和）

然后就可以了，自己歪歪（看不懂题解），一遍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
",rt);
127 //    for(int i=0;i<=K;i++){
128 //        printf("%d%c",f[i],i==K?'
':' ');
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
",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
",x);
154 //    for(int i=1;i<=dfsn[0];i++)
155 //        printf("%d%c",dfsn[i],i==dfsn[0]?'
':' ');
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
");
160 //    for(int i=0;i<=K;i++) printf("%d%c",f[i],i==K?'
':' ');
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
",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
",S[i]);
192     }
193     return 0;
194 }

View Code

总结完了点分治，NOI必胜。