MooTube G

链接

乍一看是并查集问题,但是我们需要进行一些操作才行

两者是否有关联,或者关联度是否不小于K,我们可以只进行关联至少为K的操作

比如测试用例

4 3

1 2 3

2 3 2

2 4 4

1 2

4 1

3 1

假设到了4 1的查询,我们先对操作按关联度排序,然后找到第一个关联度不小于4的位置(lower_bound),接着从这开始进行Union操作,然后答案就出来了(我们只需在根节点记录总结点数就行,不过要减1,排除自己)

一开始我想着每次查询操作都重置num数组(也就是每个信息组成的树),但是这样时间复杂度大到爆炸!!!

经过D老师的提示,我才发现关联值的查询操作包含了关联值高的,二者是包含关系(太棒了)

那我就可以也将查询操作排序,然后将答案按顺序输出,完美!!!

嗯嗯,新学会了lambda表达式(^▽^)

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>num;

struct Ask {
	int idx = 0;
	int connect = 0;
	int x = 0;
	int ans = 0;
};

struct video {
	int x = 0, y = 0;
	int connect = 0;
};

int Find(int x) {
	if (num[x] < 0) {
		return x;
	}
	else {
		return num[x] = Find(num[x]);
	}
}

void Union(int x, int y) {
	int root_x = Find(x);
	int root_y = Find(y);
	if (root_x != root_y) {
		if (num[root_x] < num[root_y]) {
			num[root_x] += num[root_y];
			num[root_y] = root_x;
		}
		else {
			num[root_y] += num[root_x];
			num[root_x] = root_y;
		}
	}
}

int query(int x) {
	return -num[Find(x)];
}

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

	int n, q;
	cin >> n >> q;
	num.resize(n + 1, -1);
	vector<video>Video(n-1);
	for (int i = 0;i < n - 1;i++) {
		cin >> Video[i].x >> Video[i].y >> Video[i].connect;
	}

	sort(Video.begin(), Video.end(), [](video& x, video& y) {
		return x.connect < y.connect;
		});
	vector<Ask>ask(q);
	for (int i = 0;i < q;i++) {
		cin >> ask[i].connect >> ask[i].x;
		ask[i].idx = i;
	}
	sort(ask.begin(), ask.end(), [](Ask x,Ask y) {
		return x.connect > y.connect;
		});
	int last = n - 1;
	for (auto& it : ask) {
		video k;
		k.connect = it.connect;
		auto IT = lower_bound(Video.begin(), Video.end(), k, [](video x,video y) {
			return x.connect < y.connect;
			});
		int idx = IT - Video.begin();
		for (int i = idx;i < last;i++) {
			Union(Video[i].x, Video[i].y);
		}
		last = idx;
		int ans = query(it.x) - 1;
		it.ans = ans;
		//cout << it.ans << '\n';
	}
	sort(ask.begin(), ask.end(), [](Ask x, Ask y) {
		return x.idx < y.idx;
		});
	for (auto it : ask) {
		cout << it.ans << '\n';
	}
}

时间复杂度:O((n+q)log n)

空间复杂度:O(n+q)