原题呈现

P6374 树上询问#

题目描述#

给定一棵 $n$ 个点的无根树，有 $q$ 次询问．

每次询问给一个参数三元组 $(a,b,c)$ ，求有多少个 $i$ 满足这棵树在以 $i$ 为根的情况下 $a$ 和 $b$ 的最近公共祖先为 $c$ ．

输入格式#

第一行 $2$ 个数，为 $n$ 和 $q$ ．

接下来 $n-1$ 行，每行 $2$ 个数，表示树的一条边．

接下来 $q$ 行，每行 $3$ 个数，为 $(a,b,c)$ ．

输出格式#

共 $q$ 行，每行一个数，为对于每个三元组的 $i$ 的个数．

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

输入输出样例 #3#

输入 #3#

输出 #3#

说明/提示#

样例 2 解释#

第一个查询的 $i$ 为 $3$ 和 $4$ ．

第二个查询的 $i$ 为 $1$ ．

数据范围#

本题按子任务测试：#

Subtask 1（ $20$ pts）： $1 \leq n \leq 1000$ ， $1 \leq q \leq 500$ ．
Subtask 2（ $15$ pts）： $1 \leq n \leq 10^{5}$ ， $1 \leq q \leq 10^{5}$ ，树退化成链．
Subtask 3（ $25$ pts）： $1 \leq n \leq 5 \times 10^{5}$ ， $1 \leq q \leq 10^{5}$ ，数据不随机．
Subtask 4（ $40$ pts）： $1 \leq n \leq 5 \times$ $10^{5}$ ， $1 \leq q \leq 2 \times 10^{5}$ ．

对于所有数据： $1 \leq n \leq 5 \times 10^{5}$ ， $1 \leq q \leq 2 \times 10^{5}$ ．

注：数据强度不高，不必卡常与快读快输．

考虑样例 2，当询问为 $(2, 5, z)$ 时，此时，

根节点	lca(2,5)
1	1
2	2
3	3
4	3
5	5

显然，不在 $2\to 5$ 这条链上的 $4$ 不可能为两节点的最近公共祖先．实际上，对于询问 $(x,y,z)$ ，不在 $x\to y$ 这条链上的所有点 $a$ ，若满足 $a=z$ ，则方案数必然为 $0$ ．因为若 $a$ 与 $x\to y$ 连通时存在一个汇入点 $b$ ，满足 $a\to b$ 和 $x\to y$ 交于点 $b$ ，且点 $b$ 在 $x\to y$ 上，则此时路径 $a\to x$ 和 $a\to y$ 会有重合（ $a\to b$ ）．因此， $a$ 不能成为 $x,y$ 的最近公共祖先．

那对于 $z$ 在 $x\to y$ 上的情况怎么办呢？那么此时首先， $z$ 自身可以作为根节点．其次，不在 $x\to y$ 上的点，且与 $z$ 连通的点可以将 $z$ 拎起来．因此，答案就是不在 $x\to y$ 上且与 $z$ 直接相连（这里指不通过 $x\to y$ 上的任何边就能够相连）的点以及 $z$ 本身的节点数量．

考虑如何 $O(1)$ 算出．显然，我们可以以 $1$ 为根建树进行一次 dfs，那么，对于询问 $(x,y,z)$ ，会有四种可能：

$z$ 不在 $x\to y$ 上．此时根据分析，输出 0．
$z$ 正好是 $x,y$ 的最近公共祖先．此时，所有可能的根节点就是 $z$ 去除含有 $x,y$ 的两颗子树（这里含有……的子树指所有以 $z$ 子节点为根节点的子树中含有该节点的子树，下同）大小，剩余的图中所有点都可以作根
$z$ 在 $x,y$ 的最近公共祖先的含有 $x$ 的子树上，如上述样例中的 $(2,5,3)$ ， $3$ 就在 $2,5$ 最近公共祖先 $1$ 的含有 $2$ 的子树上．再如下图中的 $(x,y,z)$ ，那么此时， $z$ 的子树中含有 $x$ 的子树部分（即图中节点 $u,x,D,E$ ）肯定不行（因为子树上的任意一点都需要经过 $u\to z$ ，这条边在 $x\to y$ 上），且此时除了 $z$ 子树之外的部分 $s$ （即图中点 $A,b,y,v$ ）也不能作为子节点（因为 $s$ 上的每一个点想要到达 $z$ 都需要经过 $v\to z$ ，显然 $y$ 不在 $z$ 的子树上，故 $y\to z\to x$ 也需要通过 $v\to z$ ，因此 $v\to z$ 在 $x\to y$ 上）因此答案为：所有的节点，减去 $z$ 子树中含有 $x$ 的子树大小，再减去不在 $z$ 子树中的节点．
$z$ 在 $x,y$ 的最近公共祖先的有 $y$ 的子树上，这一种和上一种相同．

小技巧：如何

O(1)

计算一个点是否是另外一个点的子孙节点．

这需要用到 dfs 序，所谓 dfs 序，就是通过 dfs 首次先序遍历到每一个节点的次序，这可以在 dfs 的时候预处理出来．节点 $u$ 的 dfs 序常记为 $\operatorname{dfn}_u$ ．不难发现，同一个子树内的节点， $dfn$ 是连续的．可以利用这个性质，若我们现在想要知道 $v$ 是否是 $u$ 的子节点，那么这个命题完全等同于：

\DeclareMathOperator{\dfn}{dfn} \dfn_u \leq \dfn_v \lt \dfn_u + size

，其中， $size$ 为 $u$ 及其子节点的数量．

可以写出代码：

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N = 5e5 + 100;
4
int n, q;
5
vector<int> e[N];
6
int f[22][N], cnt, dfn[N], sz[N], dep[N];
7

8
int LCA(int x, int y) {
9
    if (dep[x] > dep[y]) {
10
        swap(x, y);
11
    }
12
    int step = dep[y] - dep[x];
13
    for (int i = 20; i >= 0; i--) {
14
        if (step & (1 << i)) {
15
            y = f[i][y];
16
        }
17
    }
18
    if (x == y)
19
        return x;
20
    for (int i = 20; i >= 0; i--) {
21
        if (f[i][x] != f[i][y]) {
22
            x = f[i][x];
23
            y = f[i][y];
24
        }
25
    }
26
    return f[0][x];
27
}
28

29
void dfs(int t, int fa) {
30
    f[0][t] = fa;
31
    dep[t] = dep[f[0][t]] + 1;
32
    dfn[t] = ++cnt;
33
    for (int i = 0; i < e[t].size(); i++) {
34
        if (e[t][i] != fa)
35
            dfs(e[t][i], t);
36
    }
37
    for (int i = 0; i < e[t].size(); i++) {
38
        if (e[t][i] != fa)
39
            sz[t] += sz[e[t][i]];
40
    }
41
    sz[t]++;
42
}
43

44
/**
45
 * 判断 x 是不是在 y 的子树中
46
 */
47
bool isIn(int x, int y) { return dfn[y] <= dfn[x] && dfn[x] < dfn[y] + sz[y]; }
48

49
/**
50
 * 通过倍增计算以fa子节点为根节点的子树中含有dir的子树
51
 */
52
int getSubSz(int dir, int fa) {
53
    if (dir == fa) {
54
        return 0;
55
    }
56
    for (int i = 20; i >= 0; i--) {
57
        int now = f[i][dir];
58
        if (dfn[now] > dfn[fa]) {
59
            dir = now;
60
        }
61
    }
62
    return sz[dir];
63
}
64

65
signed main() {
66
    cin >> n >> q;
67
    for (int i = 1; i <= n - 1; i++) {
68
        int u, v;
69
        cin >> u >> v;
70
        e[u].push_back(v);
71
        e[v].push_back(u);
72
    }
73
    dfs(1, 0);
74
    for (int j = 1; j <= 20; j++) {
75
        for (int i = 1; i <= n; i++) {
76
            f[j][i] = f[j - 1][f[j - 1][i]];
77
        }
78
    }
79
    for (int i = 1; i <= q; i++) {
80
        int a, b, c;
81
        cin >> a >> b >> c;
82
        if (LCA(a, b) == c) {
83
            cout << n - getSubSz(a, c) - getSubSz(b, c) << endl;
84
        } else if (isIn(a, c) && !isIn(b, c)) {
85
            cout << n - getSubSz(a, c) - (n - sz[c]) << endl;
86
        } else if (!isIn(a, c) && isIn(b, c)) {
87
            cout << n - getSubSz(b, c) - (n - sz[c]) << endl;
88
        } else {
89
            cout << 0 << endl;
90
        }
91
    }
92
    return 0;
93
}

音乐

音乐

P6374 树上询问#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

输入输出样例 #3#

输入 #3#

输出 #3#

说明/提示#

样例 2 解释#

数据范围#

本题按子任务测试：#

文章分享

音乐

安吉D11-A

P6374 树上询问#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

输入输出样例 #3#

输入 #3#

输出 #3#

说明/提示#

样例 2 解释#

数据范围#

本题按子任务测试：#

文章分享