点分治

点分治

点分治,顾名思义,是在树上进行分治算法。即递归在儿子上进行分治。但是这样的算法在随机数据下表现优秀,但一旦碰到单链或者多链的情况便难以处理,于是我们要引入一下概念。

概念

  • 重心

    树的重心:某一棵树的重心即以重心为根时,其最大子树大小最小。或者说,删除重心后,其子树形成的森林尽量均匀

知道重心有什么用呢,那么重心有一个重要性质

重心的子树大小小于$n/2$

这就很有用了,显然我们以重心为根进行操作,复杂度就降到了$O(nlogn)$

证明略。。。

作用

解决树上各种奇奇怪怪的边之间关系的问题

算法流程

算法流程大概如下(其中ans为最终结果)

1
2
3
4
5
6
7
8
9
10
11
calc(i)
先求出其子树以重心为根时各个结点深度(便于计算路径长度)
计算并返回答案
对于当前节点i
求出未处理过的结点为根时,i结点子树的重心
处理i的答案
ans加上calc(i)(当前子树贡献)
枚举与i相连边,ans减去cal(son[i])(并不经过当前点的路径,重复计算)
处理该子树的重心
递归求解该子树

代码大概如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
void dfs1(int i,int fa)//求重心
{
size[i]=1;mx[i]=0;
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(v==fa||done[v])
continue;
dfs1(v,i);
size[i]+=size[v];
mx[i]=max(size[v],mx[i]);
}
mx[i]=max(now-size[i],mx[i]);
if(mx[i]<mx[root])
root=i;
}
void getdeep(int i,int fa)//计算深度
{
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(v==fa||done[v])
continue;
dep[v]=dep[i]+edg[tmp].w;
getdeep(v,i);
}
}
int calc(int i,int now)
{
dep[i]=now;
getdeep(i,0);
//计算并返回答案(根据不同题计算过程不同,此处略去)
}
void solve(int i)
{
ans+=calc(i,0);
done[i]=1;//标记已经处理过了
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(done[v])
continue;
ans-=calc(v,edg[tmp].w);/*注意这时要传递一下这个边的
路径,否则计算会出错,因为不经过当前节点 */
root=0;
now=size[v];
dfs1(v,root);
solve(root);
}
}
int main()
{
dfs1(1,0);
solve(1);
}

例题

只做过最裸的,动态的未来更新吧(今天搞搞别的分治)

树上的点对

求树上两点间距离$dis(u,v)≤k$的对数

解法:
树分治,套用以上模板,计算的时候呢,计算出来所有的$depth$后,放入一个数组,进行排序,利用类似于迟取的思想快速计算出有几对即可。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e4+1e3+7,INF=0x7fffffff;
int n,k,ans,size[N],root,dep[N],mx[N],td[N],done[N],cnt,head[N],now;
struct node{
int ne,to,w;
}edg[N*2+1];
void build(int u,int v,int w)
{
++cnt;
edg[cnt].to=v;
edg[cnt].w=w;
edg[cnt].ne=head[u];
head[u]=cnt;
}
void dfs1(int i,int fa)
{
size[i]=1;mx[i]=0;
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(v==fa||done[v])
continue;
dfs1(v,i);
size[i]+=size[v];
mx[i]=max(size[v],mx[i]);
}
mx[i]=max(now-size[i],mx[i]);
if(mx[i]<mx[root])
root=i;
}
void getdeep(int i,int fa)
{
td[++td[0]]=dep[i];
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(v==fa||done[v])
continue;
dep[v]=dep[i]+edg[tmp].w;
getdeep(v,i);
}
}
int calc(int i,int now)
{
dep[i]=now,td[0]=0;
getdeep(i,0);
sort(td+1,td+td[0]+1);
int t=0,l,r;
for(l=1,r=td[0];l<r;)
{
if(td[l]+td[r]<=k)
t+=r-l,l++;
else r--;
}
return t;
}
void solve(int i)
{
ans+=calc(i,0);
done[i]=1;
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(done[v])
continue;
ans-=calc(v,edg[tmp].w);
root=0;
now=size[v];
dfs1(v,root);
solve(root);
}
}
int main()
{
freopen("poj1741_tree.in","r",stdin);
freopen("poj1741_tree.out","w",stdout);
while(scanf("%d%d",&n,&k))
{
ans=0;
if(n==0)
break;
memset(head,0,sizeof(head));
memset(done,0,sizeof(done));
cnt=0;
root=0;
mx[0]=0x7fffffff;
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
build(u,v,w);
build(v,u,w);
}
now=1;
dfs1(1,0);
solve(1);
printf("%d\n",ans);
}
}

聪聪可可

求树上两点间路径权值和模$3$等于$0$的对数(无序)。

对于一个节点,等于$0$的有$x$对,等于$1$的有$y$对,等于$2$的有$z$对,那么一共满足的就有$x^2+2yz$对,然后还是套模板。。。。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+1e3+7;
struct node{
int ne,to,w;
}edg[N*2+1];
int n,m,cnt,head[N],size[N],mx[N],root,now,ans,mo0,mo1,mo2,done[N],dep[N],td[N];
void build(int u,int v,int w)
{
++cnt;
edg[cnt].to=v;
edg[cnt].w=w;
edg[cnt].ne=head[u];
head[u]=cnt;
}
void dfs(int i,int fa)
{
size[i]=1,mx[i]=0;
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(v==fa||done[v])
continue;
dfs(v,i);
size[i]+=size[v];
mx[i]=max(mx[i],size[v]);
}
mx[i]=max(mx[i],now-size[i]);
if(mx[i]<mx[root])
root=i;
}
void getdeep(int i,int fa)
{
if(dep[i]%3==1)
mo1++;
else
if(dep[i]%3==2)
mo2++;
else
mo0++;
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(v==fa||done[v])
continue;
dep[v]=dep[i]+edg[tmp].w;
getdeep(v,i);
}
}
int calc(int i,int now)
{
mo0=mo1=mo2=0;
dep[i]=now;
getdeep(i,0);
return mo0*mo0+mo1*mo2*2;
}
void solve(int i)
{
ans+=calc(i,0);
done[i]=true;
for(int tmp=head[i];tmp;tmp=edg[tmp].ne)
{
int v=edg[tmp].to;
if(!done[v])
{
ans-=calc(v,edg[tmp].w);
root=0;
now=size[v];
dfs(v,0);
solve(root);
}
}
}
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
freopen("cckk.in","r",stdin);
freopen("cckk.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
build(u,v,w%3);
build(v,u,w%3);
}
now=n;
mx[0]=0x7fffffff;
dfs(1,0);
solve(1);
int tmp=gcd(ans,n*n);
printf("%d/%d",ans/tmp,n*n/tmp);
}