0%

[CF1213G] Path Queries

题目

题目链接

题目大意:给出一个 $n$ 个点的树,边有边权。有 $m$ 组询问,每次询问树上所有路径中权值最大的边的权值不超过 $q$ 的路径数量。$1 \le n, m, w, q \le 200000$。

思路

考虑到如果有一条边的权值 $w$ 不大于 $q$,那对于任意的 $q’ > q$,这条边都满足条件。

也就是如果把所有询问按 $q$ 升序排序后,答案也是升序排列。

所以我们可以先把所有询问按 $q$ 升序排序。

对于每组询问,相当于找到有多少点满足这两个点之间的最大边权不超过 $q$。

如果这两个点满足条件,那么这两个点之间的任意点对也满足条件,这样就可以更新答案了。

然后就是怎么维护了。先把所有边按边权从小到大排序,然后如果当前的边的边权满足条件,就把这条边的两个端点合并,同时更新联通块大小和答案。

最后按照询问的顺序输出就行了。

注意开 long long

类似题目:[USACO18JAN] MooTube S

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

template <class T> inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

struct Edge {
LL u, v, w;
} g[200010];

struct Query {
LL k, id;
} b[200010];

LL f[200010], cnt[200010], ans[200010];
LL n, q, j = 1, s;

int unionFind(int x) { return f[x] == x ? x : f[x] = unionFind(f[x]); }

void link(int x, int y) {
int fx = unionFind(x), fy = unionFind(y);
if (fx != fy) {
s -= (((cnt[fx] * (cnt[fx] - 1)) / 2) + ((cnt[fy] * (cnt[fy] - 1)) / 2));
cnt[fy] += cnt[fx];
s += (cnt[fy] * (cnt[fy] - 1)) / 2;
f[fx] = fy;
}
}

int main() {
read(n), read(q);
for (int i = 1; i <= n; ++i) f[i] = i, cnt[i] = 1;
for (int i = 1; i < n; ++i) read(g[i].u), read(g[i].v), read(g[i].w);
for (int i = 1; i <= q; ++i) read(b[i].k), b[i].id = i;
std::sort(g + 1, g + n, [](const Edge &a, const Edge &b) {
return a.w < b.w;
} );
std::sort(b + 1, b + q + 1, [](const Query &a, const Query &b) {
return a.k < b.k;
} );
for (int i = 1; i <= q; ++i) {
while (j < n && g[j].w <= b[i].k) {
link(g[j].u, g[j].v);
++j;
}
ans[b[i].id] = s;
}
for (int i = 1; i <= q; ++i) printf("%lld ", ans[i]);
puts("");
return 0;
}