虚树
之前在主站写过一篇虚树的博客，但是主站因为忘记续费然后直接没了。。。
有一个非常显然的结论，对于$dfs$序连续的三个点$x,y,z$，有$lca(x,z)\in {lca(x,y),lca(y,z)}$，这个用分类讨论什么的很容易证明
那么建虚树就只要将所有关键点按照$dfs$排序之后，将相邻的点的$lca$加入即可
关键代码
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
| bool comp(int x, int y)
{
return dfn[x] < dfn[y];
}
int main()
{
//
scanf("%d", &m);
while (m--)
{
int cnt = read();
for (int i = 1; i <= cnt; i++)
{
x[i] = read();
flag[x[i]] = 1;
}
cnt++;
x[cnt] = 1;
std::sort(x + 1, x + cnt + 1, comp);
cnt = std::unique(x + 1, x + cnt + 1) - x - 1;
for (int i = 1, tmp = cnt; i < tmp; i++)
{
cnt++;
x[cnt] = querylca(x[i], x[i + 1]);
}
std::sort(x + 1, x + cnt + 1, comp);
cnt = std::unique(x + 1, x + cnt + 1) - x - 1;
top = 1;
stack[top] = x[1];
for (int i = 2; i <= cnt; i++)
{
while (top > 0 && deep[stack[top]] > deep[querylca(stack[top], x[i])])
{
top--;
}
if (stack[top])
{
add(stack[top], x[i], 0);
}
top++;
stack[top] = x[i];
}
solve(1, 0);
printf("%lld\n", f[1]);
edgenum = 0;
for (int i = 1; i <= cnt; i++)
{
flag[x[i]] = 0;
head[x[i]] = 0;
}
}
//
}
|