Luogu P5002 专心OI - 找祖先（图论）

题目链接

简要做法

首先对于 `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 一下统计答案即可

参考代码

#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;
}