题解：P12849 [蓝桥杯 2025 国 A] 公路【数据强度待检验】

· · 题解

P12849 [蓝桥杯 2025 国 A] 公路 题解

思路分析

这道题本质是一个 树上路径统计问题。我们要统计所有 n \times (n - 1) 个点对之间，所经过路径中不同公司的数量之和。

路径上不同公司的数量 = 经过的边所属公司的种类数 我们不妨将这个问题转化为：

对于每一条路径，统计其经过了多少种公司修建的边。

由于路径数量是 \mathcal{O}(n^2) ，无法暴力计算，我们考虑边权分组处理，转换思路：

转化思路

最终答案：

\text{答案} = \sum_{(u,v), u \ne v} \text{该路径中经过的公司数} = \sum_{\text{公司 } c} \left(n(n-1) - \sum_{\text{连通块 } x} |x|(|x|-1)\right)

其中 |x| 是公司 c 的一个连通块的大小。

DFS 实现划分连通块

这样，能在线性时间内计算出每个公司所对应的多个连通块大小，进而算出它不需要申请通行证的路径数量。

代码实现

#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<pair<int,int>>> adj; // 邻接表：{目标点, 公司编号}
vector<int> dt; // 每个点子树大小
vector<vector<int>> pc; // 每个公司分割的连通块大小列表
vector<int> hd; // 当前回溯时连通块记录的位置

// DFS1：求每个节点的子树大小
int dfs(int u, int p){
    for(auto [v, c] : adj[u]){
        if(v != p){
            dt[u] += dfs(v, u);
        }
    }
    dt[u] += 1;
    return dt[u];
}

// DFS2：分割公司连通块
void dfs1(int u, int p){
    for(auto [v, c] : adj[u]){
        if(v != p){
            int pre = hd[c];
            pc[c][pre] -= dt[v];
            pc[c].push_back(dt[v]);
            hd[c] = pc[c].size() - 1;
            dfs1(v, u);
            hd[c] = pre;
        }
    }
}

void solve() {
    int n;
    cin >> n;
    adj.resize(n+1);
    dt.resize(n+1, 0);
    pc.resize(n+1, vector<int>(1, n));
    hd.resize(n+1, 0);

    vector<bool> used(n+1, false); // 标记公司是否出现

    for(int i = 1; i < n; i++){
        int u, v, c;
        cin >> u >> v >> c;
        used[c] = true;
        adj[u].push_back({v, c});
        adj[v].push_back({u, c});
    }

    dfs(1, 0);
    dfs1(1, 0);

    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(!used[i]) continue;
        int sum = 0;
        for(auto sz : pc[i]){
            sum += sz * (sz - 1);
        }
        ans += (n * (n - 1) - sum);
    }

    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin >> t;
    while (t--) solve();
    return 0;
}

示例解释

样例输入：

4
1 2 1
1 3 1
1 4 2

结构如下：

    1
  / | \
 2  3  4

对于公司 1，删掉它的边后，图被分为三个连通块：{1} , {2} , {3} 。路径数为 1 + 1 + 1 = 3 。 对于公司 2，删掉它的边后，图被分为 {4} , {1,2,3} ，路径数为 1 + 3 \times 2 = 7 。

所以总路径数为 n(n-1) = 12 ，公司通行证数合计为 12 - 3 + 12 - 7 = 16 。

复杂度分析