分治算法综合(三)

$\text{这篇博文概括一下之前的} \textbf{点分治}$
$\text{此外阐述了树分治中的}\textbf{点分治,边分治}$
$\textbf{以及动态树分治}$

$\textbf{CDQ分治}\text{也做了概括}$

点分治总结

$\textbf{algorithm1}$
$\textbf{i) } \text{找到树的重心 } root \text{ 作为初始根节点}$
$\quad \textbf{solve}(x\leftarrow root, ans)$

$\quad \textbf{特别说明,这里只需要在 solve}(x, ans) \text{ 中使用 vis}[\cdots] \text{ 标记防止栈溢出} $
$\quad \text{为了防止其余操作在递归时候栈溢出,}\textbf{避免出现自环}$
$\quad \text{将父节点 } pa \text{也作为参数传递,进入递归}$
$\quad \textbf{getDep}(x, pa), \textbf{getRoot}(x, pa)$
$\quad \textbf{if } (y \in son(x))=pa \textbf{ or } vis[y], \textbf{break}$

$\textbf{ii) } cal(x) \textbf{ 统计点对的个数}, ans = \sum cal(x)$
$\quad \quad \text{1. } \text{在 } cal(x) \text{ 的时候, 得到每个点的 } dep[\cdots] \rightarrow vec[\cdots ]$
$\quad \quad \quad \text{并且将其缓存起来, 这一步可以通过执行 } getDep() \text{ 完成}$
$\quad \quad \text{2. } \text{根据 } vec[\cdots], \text{做相关的统计}$

$\textbf{iii) 点分治,删除根节点, 将子树 } y \textbf{ 看成无根树,递归执行}$
$\quad \quad \textbf{for } \forall y \in son(x)$
$\quad \quad \quad \text{1. 减掉 } y \text{ 作为孩子节点的统计结果}$
$\quad \quad \quad \quad \text{此时 } y \text{ 要作为无根树来统计, 要让 }ans -=cal(y)$
$\quad \quad \quad \quad \text{而 }y \text{ 作为孩子节点, 记得 } dep_y = dep_x + w(x, y)$
$\quad \quad \quad \quad \text{之后再 }ans -= cal(y)$

$\quad \quad \quad \text{2. 重新求子树 } y \text{ 作为无根树时候的树的重心}$
$\quad \quad \quad \quad sn= size_y, \textbf{ 总节点数不再是 n 个了}$

$\textbf{algorithm2}$
$\textbf{区别就在于 cal}() \textbf{ 用树状数组统计}$
$\textbf{cal}(x, ans), x\leftarrow root$

$\textbf{i) } \text{将 }dep_x \rightarrow \text{fwick}[\cdots]$
$\quad \text{fwick}.add(dep_x, 1)$

$\textbf{ii) for } \forall y \in son(x)$
$\quad \quad \text{对每一个子树 }y \text{ 建立一个 vec}[\cdots], \textbf{存储子树节点的 }dep[\cdots ]$
$\quad \quad \textbf{getDep}(y, x) \rightarrow \text{vec}[\cdots]$
$\quad \quad \textbf{此时不要将 vec}[\cdots] \textbf{ 的元素加入树状数组}$
$\quad \quad \textbf{这个保证了 }K-vec[\cdots] \textbf{ 一定是属于其他子树的点 or 根节点}$
$\quad \quad ans = \sum \text{fwick}.ask(K-vec[\cdots])$

$\quad \quad \textbf{更新完 }ans \text{ 之后再将 vec}[\cdots] \text{ 放入树状数组中}$
$\quad \quad \text{fwick}.add(vec[\cdots], 1)$

$\quad \quad \text{此外,维护一个队列 que,统计完 } ans \text{ 之后}$
$\quad \quad \text{对树状数组进行还原}$

Luogu2634

这里也是做一个树上统计
$cnt = [0, 1, 2 \mod (3)]$
$\text{统计路径和 sum, } ++cnt[sum \mod 3]$

$\textbf{套用 algorithm1 的模版,只不过多一步 } cal()$

Luogu2634

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 3;
int n;

inline ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}

class Edge {
public:
int to, w;
Edge* next;
Edge() {}
Edge(int to, int w) : to(to), w(w) {
next = NULL;
}
} edges[maxn << 1], *head[maxn];

int M = 0;

void initG() {
M = 0;
memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
edges[++M] = Edge(v, w);
edges[M].next = head[u];
head[u] = &edges[M];
}

// == gravity ==
int root = 0;
int sz[maxn];
int vis[maxn];
int sn = n;

void getRoot(int x, int pa, int& res) {
sz[x] = 1;
int maxpart = 0;
for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
if(vis[y] || y == pa) continue;
getRoot(y, x, res);

sz[x] += sz[y];
maxpart = max(maxpart, sz[y]);
}
maxpart = max(maxpart, sn - sz[x]);

if(maxpart < res) {
res = maxpart;
root = x;
}
}
// == gravity finished ==

ll cnt[mod + 3];

void dfs(int x, int pa, int dep) {
++cnt[dep % mod];
for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y] || y == pa) continue;
int dep2 = (dep + w) % mod;
dfs(y, x, dep2);
}
}


inline ll cal(int x, int dep) {
memset(cnt, 0, sizeof(cnt));
dfs(x, 0, dep);

ll ans = 1ll * cnt[0] * cnt[0] + 1ll * 2 * cnt[1] * cnt[2];
return ans;
}



// == work ==
void work(int x, ll& ans) {
vis[x] = 1;
ans += cal(x, 0);

for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y]) continue;

ans -= cal(y, w);

int res = inf;
sn = sz[y];
root = 0;
getRoot(y, 0, res);

work(root, ans);
}
}
// == work finished ==

void init() {
memset(sz, 0, sizeof(sz));
memset(vis, 0, sizeof(vis));
sn = n;

memset(cnt, 0, sizeof(cnt));
}


int main() {
freopen("input.txt", "r", stdin);
scanf("%d", &n);
init();
initG();

_for(i, 0, n - 1) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z % mod);
add(y, x, z % mod);
}

// then solve
int res = inf;
getRoot(1, 0, res);

ll ans = 0;
work(root, ans);

ll p = n * n;
ll g = gcd(ans, p);

ans /= g, p /= g;
printf("%lld/%lld\n", ans, p);
}

点分治计数问题

计数问题一般使用 $\textbf{algorithm2}$

Luogu3806

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
const int maxn = 1e5 + 10;
const int Maxn = 1e7 + 3;
const int inf = 0x3f3f3f3f;
int n, m;

int ans[maxn];
int qry[maxn];

class Edge {
public:
int to, w;
Edge* next;
Edge() {}
Edge(int to, int w) : to(to), w(w) {}
} edges[maxn << 1], *head[maxn];

int M = 0;
int K;

void initG() {
M = 0;
memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
edges[++M] = Edge(v, w);
edges[M].next = head[u];
head[u] = &edges[M];
}

int root = 0;
int sz[maxn];
int vis[maxn];
int sn = n;

void getRoot(int x, int pa, int& res) {
sz[x] = 1;
int maxpart = 0;
for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y] || y == pa) continue;

getRoot(y, x, res);
sz[x] += sz[y];

maxpart = max(maxpart, sz[y]);
}
maxpart = max(maxpart, sn - sz[x]);
if(maxpart < res) {
res = maxpart;
root = x;
}
}

int dep[maxn];
int C[Maxn << 1];

void dfs(int x, int pa, vector<int>& vec) {
vec.push_back(dep[x]);
for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y] || y == pa) continue;
dep[y] = dep[x] + w;
dfs(y, x, vec);
}
}

queue<int> buf;
inline void cal(int x) {
assert(dep[x] == 0);
C[dep[x]] = 1;
for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y]) continue;
dep[y] = dep[x] + w;
vector<int> vec;
dfs(y, x, vec);

for(auto v : vec) _rep(k, 1, m) {
//debug(v);
if(qry[k] >= v) ans[k] |= C[qry[k] - v];
}
for(auto v : vec) {
buf.push(v);
C[v] = 1;
}
}
while (buf.size()) {
int x = buf.front();
buf.pop();

C[x] = 0;
}
C[dep[x]] = 0;
}

void solve(int x) {
vis[x] = 1;
dep[x] = 0;

cal(x);

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y]) continue;

sn = sz[y];
root = 0;
int res = inf;
getRoot(y, 0, res);

solve(root);
}
}


void init() {
memset(sz, 0, sizeof(sz));
memset(vis, 0, sizeof(vis));
sn = n;
memset(dep, 0, sizeof(dep));
memset(ans, 0, sizeof(ans));
memset(C, 0, sizeof(C));
}


int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);
init();
initG();

_for(i, 1, n) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}

_rep(k, 1, m) scanf("%d", &qry[k]);

// then solve
int res = inf;
getRoot(1, 0, res);
solve(root);


_rep(k, 1, m) {
if(ans[k]) printf("AYE\n");
else printf("NAY\n");
}

}

点分树和计数问题

Luogu2664
P2664
P2664

$\textbf{注意,第二次 calculate2() 之前的一大堆操作}$
$sum -= size_y, num[color_x]-=size_y$
$\textbf{是为了去重}$
$\textbf{否则的话,在第二次 calculate2() 的时候}$
$ans[x] += (\sum)+tot2\cdot (sz[x]-sz[y])$
$\textbf{不去重的话,会导致 } (x\rightarrow y) \textbf{ 及其子树重复计数统计}$

P2664

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200

// ============================================================== //

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int n;
int M = 0;
int color[maxn];

class Edge {
public:
int to, w;
Edge *next;
Edge() {}
Edge(int to, int w) : to(to), w(w) {
next = NULL;
}
} edges[maxn << 1], *head[maxn];

void initG() {
M = 0;
memset(head, 0, sizeof(head));
}

void add(int u, int v, int w) {
edges[++M] = Edge(v, w);
edges[M].next = head[u];
head[u] = &edges[M];
}

int sn = n;
int sz[maxn];
int root = 0;
int vis[maxn];
ll ans[maxn];

void getRoot(int x, int pa, int &res) {
sz[x] = 1;
int maxpart = 0;
for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;
if(vis[y] || y == pa) continue;

getRoot(y, x, res);
sz[x] += sz[y];
maxpart = max(maxpart, sz[y]);
}
maxpart = max(maxpart, sn - sz[x]);
if(maxpart < res) {
res = maxpart;
root = x;
}
}

ll num[maxn], cnt[maxn];

void clear(int x, int pa) {
cnt[color[x]] = num[color[x]] = 0;
sz[x] = 1;

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y] || y == pa) continue;

clear(y, x);
sz[x] += sz[y];
}
}

void calculate1(int x, int pa, ll& sum) {
if(++cnt[color[x]] == 1) {
sum += sz[x];
num[color[x]] += sz[x];
}

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;
if(y == pa || vis[y]) continue;

calculate1(y, x, sum);
}

--cnt[color[x]];
}

void change(int x, int pa, int sgn, ll& sum) {
if(++cnt[color[x]] == 1) {
sum += sgn * sz[x];
num[color[x]] += sgn * sz[x];
}

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(y == pa || vis[y]) continue;

change(y, x, sgn, sum);
}
--cnt[color[x]];
}

void calculate2(int x, int pa, int cnt2, int other, ll& sum) {
if(++cnt[color[x]] == 1) {
cnt2++;
sum -= num[color[x]];
}

ans[x] += sum + 1ll * other * cnt2;

for(const Edge *e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;

if(vis[y] || y == pa) continue;
calculate2(y, x, cnt2, other, sum);
}

if(--cnt[color[x]] == 0) {
cnt2--;
sum += num[color[x]];
}
}

void work(int x, ll& sum) {
vis[x] = 1;
sum = 0;
clear(x, -1);

calculate1(x, -1, sum);
ans[x] += 1ll * sum;

for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
int w = e->w;
if(vis[y]) continue;

++cnt[color[x]];
change(y, x, -1, sum);
sum -= sz[y];
num[color[x]] -= sz[y];

calculate2(y, x, 0, sz[x] - sz[y], sum);

change(y, x, 1, sum);
sum += sz[y];
num[color[x]] += sz[y];
--cnt[color[x]];
}

for(const Edge* e = head[x]; e; e = e->next) {
int y = e->to;
if(vis[y]) continue;

root = -1;
sn = sz[y];
int res = inf;
getRoot(y, -1, res);

work(root, sum);
}
}

void init() {
sn = n;
memset(sz, 0, sizeof(sz));
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
memset(num, 0, sizeof(num));
memset(cnt, 0, sizeof(cnt));
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d", &n);
initG();
init();

_rep(i, 1, n) scanf("%d", &color[i]);
_for(i, 1, n) {
int x, y;
scanf("%d%d", &x, &y);
add(x, y, 1);
add(y, x, 1);
}

// input data finished
root = -1;
ll sum = 0;
int res = inf;
getRoot(1, -1, res);

work(root, sum);

_rep(i, 1, n) printf("%lld\n", ans[i]);
}