【LG4185】[USACO18JAN]MooTube

题面

洛谷

题解

先将所有操作和询问离线

然后按照边权从大到小将操作和询问排序

利用\(two\;pointers\)，每次扫到一个询问，将边权大于等于它的边的两点全部都并起来

因为边权大的满足，那么边权小的一定也能满足

对于每个询问，直接查它联通块的\(size\)即可

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline int gi() {

	register int data = 0, w = 1;

	register char ch = 0;

	while (!isdigit(ch) && ch != '-') ch = getchar();

	if (ch == '-') w = -1, ch = getchar();

	while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar();

	return w * data;

}

const int MAX_N = 1e5 + 5;

struct Query { int k, v, id; } q[MAX_N];

struct Edge { int u, v, w; } e[MAX_N];

bool operator < (const Query &l, const Query &r) { return l.k > r.k; }

bool operator < (const Edge &l, const Edge &r) { return l.w > r.w; }

int N, Q, fa[MAX_N], size[MAX_N], ans[MAX_N];

int getf(int x) { return (x == fa[x]) ? x : (fa[x] = getf(fa[x])); }

void unite(int x, int y) { x = getf(x), y = getf(y); if (x != y) fa[x] = y, size[y] += size[x]; }

int main () {

	N = gi(), Q = gi();

	for (int i = 1; i < N; i++) e[i].v = gi(), e[i].u = gi(), e[i].w = gi();

	for (int i = 1; i <= Q; i++) q[i].k = gi(), q[i].v = gi(), q[i].id = i;

	sort(&e[1], &e[N]); sort(&q[1], &q[Q + 1]);

	for (int i = 1; i <= N; i++) fa[i] = i, size[i] = 1;

	for (int i = 1, j = 1; i <= Q; i++) {

		while (e[j].w >= q[i].k && j < N) unite(e[j].u, e[j].v), ++j;

		ans[q[i].id] = size[getf(q[i].v)] - 1;

	}

	for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);

	return 0;

}