WA * 7 求条
查看原帖
WA * 7 求条
902351
Little_x_starTYJ楼主2025/6/19 16:06
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
	int u, v, id;
} f[200010];
stack<node> s;
vector<int> v[200010];
int n, res, ans[200010], fa[200010], siz[200010], cnt[200010];
inline int find(int x) {
	if (fa[x] == x) {
		return fa[x];
	}
	return fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) {
		res -= min(siz[x], cnt[x]);
		cnt[x]++;
		res += min(siz[x], cnt[x]);
		s.push({x, x, 0});
	} else {
		res -= min(siz[x], cnt[x]) + min(siz[y], cnt[y]);
		if (siz[x] < siz[y]) {
			swap(x, y);
		}
		fa[y] = x;
		siz[x] += siz[y];
		cnt[x] += cnt[y] + 1;
		res += min(siz[x], cnt[x]);
		s.push({x, y, 1});
	}
}
inline void split() {
	int x = s.top().u, y = s.top().v, p = s.top().id;
	s.pop();
	if (p) {
		res -= min(siz[x], cnt[x]);
		fa[y] = y;
		siz[x] -= siz[y];
		cnt[x] -= cnt[y] + 1;
		res += min(siz[x], cnt[x]) + min(siz[y], cnt[y]);
	} else {
		res -= min(siz[x], cnt[x]);
		cnt[x]--;
		res += min(siz[x], cnt[x]);
	}
}
inline void dfs(int x, int fa) {
	merge(f[x].u, f[x].v);
	ans[x] = res;
	for (auto u : v[x]) {
		if (u ^ fa) {
			dfs(u, x);
		}
	}
	split();
}
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	int a, b;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		f[i] = {a, b, i};
		fa[a] = a, siz[a] = 1, cnt[a] = 0;
		fa[b] = b, siz[b] = 1, cnt[b] = 0;
	}
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1, 0);
	for (int i = 2; i <= n; i++) {
		cout << ans[i] << ' ';
	}
	return 0;
}
2025/6/19 16:06
加载中...