Luogu P3218 #

题目大意：#

求取被指定的多条路径覆盖的树中找出被覆盖次数最多的节点

!!INPUT：#

第一行
- N: 节点
- K: 路径数
接下来N - 1行，每一行：
- x y: 节点x与y之间有通路
接下来K行：
- s t: 路径端点

思路#

考虑使用链式前向星建树。

遍历路上的节点，经过一次加1。

题中路径已知两端点，记起点为 $u$ , 终点为 $v$ 则路径为

u \to lca(u, v) \to v

若直接遍历，则时间复杂度为 $O(NK)$ ，按题目数据最多遍历 $5 \times 10^{10}$ , 这是不能接受的。

考虑使用树上差分优化。

关于前缀和 & 差分的知识，可以去OI-WiKi中学习。

如果要对结点 $x$ 和 $y$ 之间的路径上的所有点权都加 $v$ ，可以对它的差分序列 $\{D_x\}$ 做如下操作：
$\begin{aligned} D_x &\gets D_x + v, \\ D_{\operatorname{lca}(x, y)} &\gets D_{\operatorname{lca}(x, y)} - v,\\ D_y &\gets D_y + v, \\ D_{\operatorname{fa}(\operatorname{lca}(x, y))} &\gets D_{\operatorname{fa}(\operatorname{lca}(x, y))} - v. \end{aligned}$
在所有修改操作完成后，可以计算一次子树和，就能得到更新后的点权。

倍增求LCA#

首先第一遍DFS预处理数组，得到二维倍增数组 $fa$ 及深度数组 depth。fa[u][i]表示节点i往上走 $2^i$ 步的父节点。

接下来进行LCA查询，具体步骤：跳、跳、跳……然后就到LCA了。

从最低节点出发，往上跳diff步即可。具体操作：

1
for (int i = 0; i <= LOG; i++)
2
    if (diff & (1 << i)) // 若 diff 的二进制第 i 位为 1
3
        u = fa[u][i];

再两个点从同一高度出发，~~一起蹦蹦跳跳~~直到两点相同。虽然使用while循环可以优化一丢丢，但是这里还是给出for循环的代码：

1
for (int i = 0; i <= LOG; i++)
2
    if (fa[u][i] != fa[v][i])
3
    {
4
        u = fa[a][i];
5
        v = fa[b][i];
6
    }

$lca(u, v)$ 即为此时的 $u = v$ 的父节点即 $fa\_{u,0}$ 。

树上差分#

树上差分和一维差分略有不同。树上差分是子节点**“在后续的累加过程中，要向它的父节点（以及自己）传递多少值”**。

例如对于树：

1
graph TD
2
1/0 --> 2/0
3
1/0 --> 3/0
4
2/0 --> 4/0
5
2/0 --> 5/0
6
3/0 --> 6/0
7
3/0 --> 7/0

要给路径 $2 \to 1 \to 7$ 加上 $1$ , 只需要给

D_7 \leftarrow D_7 + 1 \\ D_2 \leftarrow D_2 + 1\\ D_1 \leftarrow D_1 - 1\\

如果 $lca(u,v)$ 不是根节点，则 $father(lca(u, v))$ 也需要自减。

因为在 $D_u$ 和 $D_v$ 自增的过程中， $lca(u,v)$ 及其以上的所有节点的值都相应地减了两个 $1$ ，因此给 $D_{lca(u,v)}$ 及其父节点各自减一刚好可以抵消。

在最后结束时，使用前缀和合并差分数组即可得出初始值。

注意：需要使用后序遍历（即左->右->根的顺序），因为根节点需要统计所有子节点的贡献（直接在递归子节点后加上子节点的值即可）。

**提示：**在后序遍历之前记得先初始化节点值为差分值（因为也包括它自己的贡献）

示例代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int LOG = 20;
5
const int MAXN = 5e4 + 10;
6

7
int fa[MAXN][LOG << 2], depth[MAXN], D[MAXN], val[MAXN];
8
vector<int> tree[MAXN];
9

10
void dfs(int x, int father)
11
{
12
    fa[x][0] = father;
13
    for (int i = 1; i <= LOG; i++)
14
    {
15
        fa[x][i] = fa[fa[x][i-1]][i-1]; // 一分为二
16
    }
17
    for (auto child: tree[x])
18
    {
19
        if (child == fa[x][0]) continue;
20
        depth[child] = depth[x] + 1; // 深度+1
21
        dfs(child, x);
22
    }
23
}
24

25
int lca(int u, int v)
26
{
27
    if (depth[v] > depth[u]) swap(u, v);
28
    int diff = depth[u] - depth[v];
29
    for (int i = 0; i <= LOG; i++)
30
        if (diff & (1 << i)) // 若 diff 的第 i 位为 1
31
            u = fa[u][i];
32
    if (u == v) return u;
33
    if (fa[u][0] == fa[v][0]) return fa[u][0];
34
    for (int i = LOG; i >= 0; i--)
35
        if (fa[u][i] != fa[v][i])
36
        {
37
            u = fa[u][i];
38
            v = fa[v][i];
39
        }
40
    return fa[u][0];
41
}
42

43
void accumulate(int x, int father)
44
{
45
    val[x] = D[x];
46
    for (auto child: tree[x])
47
    {
48
        if (child == father) continue;
49
        accumulate(child, x);
50
        val[x] += val[child];
51
    }
52
}
53

54
signed main()
55
{
56
    int n, k;
57
    cin >> n >> k;
58
    for (int i = 1; i < n; i++)
59
    {
60
        int u, v;
61
        cin >> u >> v;
62
        tree[u].push_back(v);
63
        tree[v].push_back(u);
64
    }
65

66
    dfs(1, 0); // 根节点的爸爸是 0
67

68
    for (int i = 1; i <= k; i++)
69
    {
70
        int s, t;
71
        cin >> s >> t;
72

73
        int l = lca(s, t);
74

75
        ++D[s];
76
        ++D[t];
77
        --D[l];
78

79
        if (fa[l][0])
80
            --D[fa[l][0]];
81
    }
82

83
    accumulate(1, 0);
84

85
    int ans = -0x3f3f3f3f;
86
    for (int i = 1; i <= n; i++)
87
    {
88
        ans = max(ans, val[i]);
89
    }
90

91
    cout << ans << '\n';
92

93
    return 0;
94
}

Luogu P3218#