咋没人写tarjan? 只过#1悬棺
查看原帖
咋没人写tarjan? 只过#1悬棺
1392084
yaoyunxiang楼主2025/7/31 14:51
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

vector<int> g[N];
vector<pair<int, int>> q[N];
int diff[N], fa[N];
bool vis[N];

struct DSU {
	int p[N];
	void init(int n) {
		for (int i = 1; i <= n; ++i) p[i] = i;
	}
	int find(int x) {
		return p[x] == x ? x : p[x] = find(p[x]);
	}
	void unite(int x, int y) {
		p[find(x)] = find(y);
	}
} dsu;

void tarjan(int u, int parent) {
	vis[u] = true;
	fa[u] = parent;
	for (int v : g[u]) {
		if (v == parent) continue;
		if (!vis[v]) {
			tarjan(v, u);
			dsu.unite(v, u);
		}
	}
	for (auto &query : q[u]) {
		int v = query.second;
		if (vis[v]) {
			int l = dsu.find(v);
			diff[u]++;
			diff[v]++;
			diff[l]--;
			if (fa[l] != -1) diff[fa[l]]--;
		}
	}
}

void dfs(int u, int p) {
	for (int v : g[u]) {
		if (v == p) continue;
		dfs(v, u);
		diff[u] += diff[v];
	}
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n, k;
	cin >> n >> k;

	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	for (int i = 1; i <= k; i++) {
		int x, y;
		cin >> x >> y;
		q[x].push_back({i, y});
//		q[y].push_back({i, x});
	}

	dsu.init(n);
	memset(vis, 0, sizeof(vis));
	memset(fa, -1, sizeof(fa));
	memset(diff, 0, sizeof(diff));

	tarjan(1, -1);
	dfs(1, -1);
	
//	for(int i = 1 ; i <= n ; i ++){
//		cout << diff[i] << "\n";
//	}
	cout << *max_element(diff + 1 , diff + n + 1);
	return 0;
}
2025/7/31 14:51
加载中...