板子求条
查看原帖
板子求条
1234924
lsd110504lsd楼主2025/8/4 14:34
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
int n, m, q;
const int N = 3e5+520;
int Dp[N], fa[N], res = 0, ans[N];
vector<int> G[N];
inline int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool vis[N];
inline void Dfs(int u, int f) {
//	Dp[u]=1;
	for (auto v : G[u]) {
		if (v == f)	continue;
		Dfs(v, u);
		res = max(res, Dp[u] + Dp[v] + 1);
		Dp[u] = max(Dp[u], Dp[v] + 1);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)	fa[i] = i;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
		fa[find(x)] = find(y);
	}
	for (int i = 1; i <= n; i++) {
		if (vis[find(i)])	continue;
		vis[find(i)] = true;
		Dfs(find(i), 0);
		ans[find(i)] = res;
		res = 0;
		cerr << ans[find(i)] << endl;
	}
	for (int i = 1; i <= q; i++) {
		int opt;
		cin >> opt;
		if (opt & 1) {
			int x;
			cin >> x;
			cout << ans[find(x)] << endl;
		} else {
			int x, y;
			cin >> x >> y;
			ans[find(y)] = max({ans[x], ans[y], (ans[x] + 1) / 2 + (ans[y] + 1) / 2 + 1});
			fa[find(x)] = find(y);
		}
	}
	return 0;
}
2025/8/4 14:34
加载中...