[蓝桥杯 2022 国 B] 机房

题意

给一棵 $n$ 个点的树，每个点代表一台电脑。

如果一台电脑直接连了 $d$ 根网线，那么信息每经过这台电脑一次，就会产生 $d$ 单位时间延迟。

查询很多次：

从电脑 $u$ 向电脑 $v$ 发送信息
最短时间是多少

因为原图是一棵树，所以 $u$ 到 $v$ 的路径唯一，最短时间就是：

这条路径上所有点的延迟之和

这里发送点和接收点也要算一次；如果 $u = v$ ，那就只算这一个点本身的延迟。

样例树

样例树结构如下：

graph G {
  1 -- 2;
  1 -- 3;
  2 -- 4;
}

各点度数分别是：

$deg[1] = 2$
$deg[2] = 2$
$deg[3] = 1$
$deg[4] = 1$

比如查询 2 -> 3，路径是 2-1-3，答案就是：

$2 + 2 + 1 = 5$

思路

先看一个最直接的小数据暴力：

cpp

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76// brute.cpp：每次查询直接在树上找唯一路径，把路径上的点度数加起来。
// 这个做法复杂度较高，只适合小数据理解题意和对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, m;
vector<int> g[MAXN];
int deg[MAXN];
int parent_arr[MAXN];
bool vis[MAXN];

bool dfs_find(int u, int target, int fa) {
    if (u == target) {
        return true;
    }

    for (size_t i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) {
            continue;
        }
        parent_arr[v] = u;
        if (dfs_find(v, target, u)) {
            return true;
        }
    }
    return false;
}

long long query_path_sum(int u, int v) {
    for (int i = 1; i <= n; i++) {
        parent_arr[i] = 0;
    }

    dfs_find(u, v, 0);

    long long ans = 0;
    int x = v;
    while (x != u) {
        ans += deg[x];
        x = parent_arr[x];
    }
    ans += deg[u];

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        deg[i] = 0;
    }

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    while (m--) {
        int u, v;
        cin >> u >> v;
        cout << query_path_sum(u, v) << '\n';
    }

    return 0;
}

暴力做法就是：

每次查询在树上找出 $u$ 到 $v$ 的唯一路径
把路径上所有点的度数累加起来

这个方法很直观，但查询多的时候，每次都重新找路径会慢。

关键观察是：

题目本质上就是“树上路径点权和”
每个点的点权固定等于它的度数

于是可以把题目转成一个标准模型：

任选 $1$ 为根
设 $\text{prefix\_sum}[u]$ 表示从根到 $u$ 的路径点权和
对于两点 $u, v$ ，它们路径和可以用 LCA 拆出来

设 $p = \text{lca}(u, v)$ ，那么：

根到 $u$ 的路径和是 $\text{prefix\_sum}[u]$
根到 $v$ 的路径和是 $\text{prefix\_sum}[v]$
根到 $p$ 的那一段被重复算了两次

所以答案是：

$\text{prefix\_sum}[u] + \text{prefix\_sum}[v] - 2 \cdot \text{prefix\_sum}[p] + \text{deg}[p]$

最后为什么还要加回 $\text{deg}[p]$ ？

因为：

$\text{prefix\_sum}[p]$ 被减了两次
但 LCA 点本身在真实路径里应该保留一次

因此只要预处理好：

每个点的度数
每个点到根的路径和
倍增 LCA

每次询问就能在 $O(log n)$ 内回答。

代码

cpp

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const int LOG = 18;

int n, m;
vector<int> g[MAXN];
int deg[MAXN];

int depth_arr[MAXN];
int up[MAXN][LOG];
long long prefix_sum[MAXN];  // 根到当前点路径上的点权和（点权 = 度数）

void init_graph(int n) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        deg[i] = 0;
        depth_arr[i] = 0;
        prefix_sum[i] = 0;
        for (int j = 0; j < LOG; j++) {
            up[i][j] = 0;
        }
    }
}

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
    deg[u]++;
    deg[v]++;
}

void build_lca(int root) {
    vector<int> st;
    st.push_back(root);
    up[root][0] = 0;
    depth_arr[root] = 0;
    prefix_sum[root] = deg[root];

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();

        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == up[u][0]) {
                continue;
            }

            up[v][0] = u;
            depth_arr[v] = depth_arr[u] + 1;
            prefix_sum[v] = prefix_sum[u] + deg[v];

            for (int j = 1; j < LOG; j++) {
                up[v][j] = up[up[v][j - 1]][j - 1];
            }

            st.push_back(v);
        }
    }
}

int kth_ancestor(int u, int k) {
    for (int j = 0; j < LOG; j++) {
        if (k & (1 << j)) {
            u = up[u][j];
        }
    }
    return u;
}

int lca(int a, int b) {
    if (depth_arr[a] < depth_arr[b]) {
        swap(a, b);
    }

    a = kth_ancestor(a, depth_arr[a] - depth_arr[b]);
    if (a == b) {
        return a;
    }

    for (int j = LOG - 1; j >= 0; j--) {
        if (up[a][j] != up[b][j]) {
            a = up[a][j];
            b = up[b][j];
        }
    }

    return up[a][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    init_graph(n);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    build_lca(1);

    while (m--) {
        int u, v;
        cin >> u >> v;

        int p = lca(u, v);
        long long ans = prefix_sum[u] + prefix_sum[v] - 2LL * prefix_sum[p] + deg[p];
        cout << ans << '\n';
    }

    return 0;
}

复杂度

预处理：

建树和点度数统计： $O(n)$
倍增祖先表： $O(n log n)$

每次查询：

求一次 LCA： $O(log n)$

空间复杂度：

$O(n log n)$

总结

这题虽然题面说的是“网络传输时间”，但真正落到算法上只有一句话：

路径代价 = 路径上所有点的度数和

一旦看成树上路径点权和，就会自然想到：

根到点前缀和
LCA 拆路径

所以它本质是一道很标准的：

倍增 LCA + 路径点权和

的树上查询题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[蓝桥杯 2022 国 B] 机房

目录

题意

样例树

思路

代码

复杂度

总结

一图流解析