概述

树分治分为点分治和边分治
一般边分治常数略大,我们只介绍点分治

先选取一个点,将无根树转为有根树,然后对所有子树进行递归处理
为了保证复杂度,我们每次选取树的重心作为根

复杂度 $O(nlogn)$

模板

求树上路径权值和小于K的路径个数(点对统计)

对于路径通过当前的根的答案
记d[u]为当前节点到根的路径权值

ans = cnt(d[u] + d[v] <= K) - cnt(d[u] + d[v] <= k 且 u,v在同一棵子树)

对于cnt的统计,我们排序后利用d的单调性来线性统计,得到一个$O(nlogn)$的算法

复杂度 $O(nlog^2n)$

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define mp std::make_pair
#define fi first
#define se second

const int maxn = 1e4 + 10;
int n,k;
std::vector<std::pair<int,int> > G[maxn];
std::vector<int> dd;
int root,size,ans;
int sz[maxn],f[maxn],d[maxn],done[maxn];

void getroot(int u,int fa=0)
{
sz[u] = 1,f[u] = 0;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i].fi;
if(v == fa || done[v]) continue;
getroot(v,u);
sz[u] += sz[v];
f[u] = std::max(f[u],sz[v]);
}
f[u] = std::max(f[u],size - sz[u]);
if(f[u] < f[root]) root = u;
}

void getd(int u,int fa=0)
{
dd.push_back(d[u]);
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i].fi;
if(v == fa || done[v]) continue;
d[v] = d[u] + G[u][i].se;
getd(v,u);
}
}

int cal(int u,int init)
{
dd.clear(); d[u] = init;
getd(u);
sort(dd.begin(),dd.end());
int res = 0,l,r;
for(l=0,r=dd.size()-1;l<r;)
if(dd[l] + dd[r] <= k) res += r-l,++l;
else --r;
return res;
}

void gao(int u)
{
ans += cal(u,0);
done[u] = 1;
for(int i=0;i<G[u].size();++i)
{
int v = G[u][i].fi;
if(done[v]) continue;
ans -= cal(v,G[u][i].se);
f[0] = size = sz[v];
root = 0;
getroot(v);
gao(root);
}
}

int main()
{
//freopen("input.txt","r",stdin);
while(~scanf("%d %d",&n,&k) && n+k)
{
F(i,1,n) G[i].clear();
memset(done,0,sizeof done);
F(i,1,n-1)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
G[u].push_back(mp(v,w));
G[v].push_back(mp(u,w));
}
f[0] = size = n;
root = 0;
getroot(1);
ans = 0;
gao(root);
printf("%d\n",ans);
}
return 0;
}

题目

SPOJ-FTOUR2

一棵树,n个结点,每条边上有权值,并且有m个结点标记为黑色
问不超过k个黑结点的路径的最大权值

我们统计经过根结点的最优值,然后递归处理子树
我们用 d[i] 表示 经过黑结点个数小于等于i的最优值
然后用 g[i] 表示 经过黑结点个数等于i的最优值

即求 max(d[i] + g[k-color[root]-i])

可以发现答案与子树的顺序无关
我们将所有子树按 路径中包含最多的黑结点 从小到大排序
然后我们按排序后的顺序,每次求g[],更新 d[]

cf715C

树的每条边上有一个数位(1-9)
统计有多少条链,使得其表示的十进制数可以被m整除
(不同方向统计两次)

我们dfs所有从根出发%m的值
按顺序记为 d1[v],逆序记为 d2[v]

$d2_u \times 10^{dep_v}+ d1_v \equiv 0\ mod\ m$

$d2_u \equiv -d1_v \times \frac{1}{10^{dep_v}}\ mod\ m$

可以预处理出所有$10^n$的逆元,先dfs d1,然后dfs d2顺便统计
注意若
$d2_v = -d1_v \times \frac{1}{10^{dep_v}}\ mod\ m$

则说明这条链正向与反向构成了一个合法答案,应该去掉

复杂度 $O(nlog^2n)$

参考