Path Queries 题解

· · 题解

原题传送门

题目描述

分析

这是一道 并查集 好题。

首先，我们需要明白当第 i 条边的边权作为简单路径中最大的边权时，此路径上的所有边权都应不大于此第 i 条边的边权。由此，我们容易想到先将每一条边按边权升序排序，再从小到大枚举每一条边。做第 i 条边时，设 sz[u] 表示节点 u 所在集合的大小，则它对权值 w_i 的贡献为 sz_{u_i} \times sz_{v_i}，然后用 并查集 合并左右区块。时间复杂度 O(n \log n)。

题目中让我们求最大权值不大于 q 的简单路径数量，于是，我们可以先用数组 ans 保存对于每一个权值的数量，再对其进行前缀和，得出题目所求。时间复杂度为 O(m)。

总时间复杂度为 O(n \log n + m)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn = 2e5;
const int N = mxn + 10;
ll ans[N]; int n, m, fx, fy, sz[N], f[N], x;
struct node { int u, v, w; } e[N];
int get_fa(int x) { if(x == f[x]) return x; return f[x] = get_fa(f[x]); }
bool cmp(node pre, node nxt) { return pre.w < nxt.w; }
signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i < n; ++ i) cin >> e[i].u >> e[i].v >> e[i].w;
    sort(e + 1, e + n, cmp);//对边按权值进行升序排序
    for(int i = 1; i <= n; ++ i) f[i] = i, sz[i] = 1;//并查集初始化
    for(int i = 1; i < n; ++ i) {
        fx = get_fa(e[i].u), fy = get_fa(e[i].v);//求得祖先
        ans[e[i].w] += (ll) sz[fx] * sz[fy];//计算贡献
        f[fx] = fy, sz[fy] += sz[fx];//合并区块
    }
    for(int i = 1; i <= mxn; ++ i) ans[i] += ans[i - 1];//前缀求答案
    while(m --) cin >> x, cout << ans[x] << ' ';
    return 0;
}