Luogu P5002」专心OI - 找祖先 - 搜索

给定 1 棵 N 个节点的树,并钦定 M 个点

对于被钦定的点 `u`,求有多少组点对 `(i,j)` 的 LCA 是 `u`

`N \leq 10^4`

`M \leq 5 \times 10^4`

「Luogu P5002」

首先对于 `u` 这个点为 LCA 时,点对肯定是在不同的子树中

  • `(i,j)` 的其中一个点是 `u` ,`ans = size_u \times 2 - 1`

  • `(i,j)` 中不含 `u`,

    设 `u` 一共有 `k` 棵子树

    `ans = \sum_{i=1}^k \sum_{j=1}^k size_i \times size_j (i \ne j)`

    `ans = \sum_{i=1}^k \sum_{j=1}^k size_i \times size_j - \sum_{i=1}^k size_i^2`

    `ans = \sum_{i=1}^k size_i \times (size_u - 1) - \sum_{i=1}^k size_i^2`

    `ans = (size_u - 1) \times (size_u - 1) - \sum_{i=1}^k size_i^2`

    `ans = (size_u - 1)^2 - \sum_{i=1}^k size_i^2`

两个情况加起来

`ans = size_u \times 2 - 1+(size_u - 1)^2 - \sum_{i=1}^k size_i^2`

`ans = size_u^2 - \sum_{i=1}^k size_i^2`

dfs 一下统计答案即可

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
#include <stdio.h>
#include <algorithm>

const int N = 1e4 + 5;
const int M = 2e4 + 5;
const int LOG2N = 15;

int n, root, m;
int head[N], num_edge;
int size[N], sum[N], ans[N];

struct Node
{
int next, to;
} edge[M];

void add_edge(int u, int v)
{
edge[++num_edge].next = head[u];
edge[num_edge].to = v;
head[u] = num_edge;
}

void dfs(int u, int father)
{
size[u] = 1;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if (v != father)
{
dfs(v, u);
size[u] += size[v];
sum[u] += size[v] * size[v];
}
}
ans[u] = size[u] * size[u] - sum[u];
}

int main()
{
scanf("%d%d%d", &n, &root, &m);
for (int i = 1; i < n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
dfs(root, 0);
for (int i = 1; i <= m; i++)
{
int x;
scanf("%d", &x);
printf("%d\n", ans[x]);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×