https://www.luogu.com.cn/problem/P5904
题意
求在一个树内有多少个三元组$(i,j,k)$满足 $dis(i,j)=dis(i,k)=dis(j,k)$
思路
假定,我们对于所有的三元组都处理成如下图所示的模样。
其中 I B K J 都是 点 A 的子树。
我们定义如下的变量。
F[u][i] --> 表示在点 u 的所有子结点中到达点 u 长度为 i 的个数。
G[u][i] --> 表示如上的二元组,连接到的中心节点 B 到达点 A 还剩下来的长度。
如果不明白看下图。
那么如果我们对于点 u ,其子树 v 我们的答案可以由 F[u][i] * G[v][i + 1] + F[v][i] + G[u][i + 1]
更新。
那么我们再来看状态转移方程。
对于一个树 u
而言其所有子树 v
,我们需要逐个更新,由于我们的 F\G
的状态都可以由子树的状态更新,因此,我们可以采用长链剖分的方法降低时间复杂度。
我们来看剩下了的该如何更新。
- 首先,我们每升一级,我们的
G[v][i]
归入到G[u][i-1]
以及F[v][i]
要归入到F[u][i + 1]
。 - 然后我们在看,
G[u][i]
可以由F[u][i] * F[v][i - 1]
归入。 - 最后,考虑到
G[u][i]
可以被F[u][i]
影响,因此,我们最后更新F
即可。
那么最终答案
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
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
vector<int> E[N];
int buff[N << 4];
int *F[N];
int *G[N];
int *pos = buff;
int len[N];
int son[N];
void get_son(int u,int fa = -1) {
for (auto v : E[u]) {
if(v == fa) continue;
get_son(v , u);
if(len[v] > len[u]) {
len[u] = len[v];
son[u] = v;
}
}
len[u] ++ ;
}
void mery(int x) {
F[x] = pos;
pos += len[x] * 2 + 1;
G[x] = pos;
pos += len[x] * 2 + 1;
}
long long ans = 0;
void get_ans(int u,int fa = -1) {
if(son[u]) {
F[son[u]] = F[u] + 1;
G[son[u]] = G[u] - 1;
get_ans(son[u] , u);
}
F[u][0] = 1;
ans += G[u][0];
for (auto v : E[u]) {
if(v == fa || v == son[u]) continue;
mery(v);
get_ans(v , u);
for (int i = 1 ; i <= len[v] ; i ++ )
ans += F[u][i - 1] * G[v][i] +
F[v][i - 1] * G[u][i];
for (int i = 1 ; i <= len[v] ; i ++ )
G[u][i - 1] += G[v][i];
for (int i = 1 ; i <= len[v] ; i ++ )
G[u][i] += F[u][i] * F[v][i - 1];
for (int i = 1 ; i <= len[v] ; i ++ )
F[u][i] += F[v][i - 1];
}
}
int main() {
int n ; cin >> n ;
for (int i = 1 ; i < n ; i ++ ) {
int x , y ; cin >> x >> y ;
E[x].push_back(y);
E[y].push_back(x);
}
get_son(1);
mery(1);
get_ans(1);
cout << ans << '\n';
return 0;
}
PREVIOUS连珠线
NEXTLife Is A Game