Submission #70262035

---

Source Code Expand

#include<bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
using namespace std;
int n;
vector<vector<int> > g;
vector<int> dep;
vector<PII> mx, ma, ans;
void dfs0(int u = 1, int p = 0) {
//	cout << u << " " << p << "\n";
	dep[u] = dep[p] + 1;
	mx[u] = {0, u}; ma[u] = {-1, 0};
	for (auto v : g[u]) if (p != v) {
		dfs0(v, u);
		PII a = mx[v];
		a.first++; 
		if (a >= mx[u]) {
			ma[u] = mx[u]; mx[u] = a;
		}
		else if (a >= ma[u]) ma[u] = a;
	}
//	mx[u].first -= dep[u]; ma[u].first -= dep[u];
//	cout << u << " " << mx[u].first << " " << mx[u].second << " " << ma[u].first << " " << ma[u].second << "\n";
}
void dfs(int u = 1, int p = 0, PII up = {-1, 0}) {
//	cout << u << " " << mx[u].first << " " << mx[u].second << " " << up.first << " " << up.second << "\n";
	ans[u] = max(mx[u], up);
	up.first++;
	for (auto v : g[u]) if (v != p) {
		PII a;
		if (mx[u].second == mx[v].second) {
			a = ma[u]; a.first++;
			dfs(v, u, max(up, a));
			continue;
		}
		a = mx[u]; a.first++;
		dfs(v, u, max(up, a));
	}
}

inline void solve() {
	cin >> n;
	g.resize(n + 1); ans.resize(n + 1);
	dep.resize(n + 1); mx.resize(n + 1); ma.resize(n + 1);
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
//	for (int i = 1; i <= n; i++) {
//		for (auto v : g[i]) cout << v << " ";
//		cout << "\n";
//	}
	dep[0] = -1;
	dfs0(); dfs();
	for (int i = 1; i <= n; i++) cout << ans[i].second << "\n";
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
//	cin >> t;
	while (t--) solve();
	return 0;
}

Submission Info

Judge Result