RT, Wa on Test3 Line 1

思路：用 vector 存储每一条节点所在长链的信息，倒序存储，即 vector 最后一个元素表示与 u 距离为 0 的节点个数，倒数第二个表示与 u 距离为 1 的节点个数，依次类推

#include<bits/stdc++.h>
#define int long long
#define cint const int&
using namespace std;

const int maxn = 1e6 + 10;
vector<int>* d[maxn];
int ans[maxn], dep[maxn], son[maxn], cnt, head[maxn];
struct {
	int nxt, v;
}edge[maxn << 1];
inline void addedge(cint u, cint v) {
	edge[++cnt] = { .nxt = head[u],.v = v };
	head[u] = cnt;
}

void dfs(cint u, cint fa) {
	int maxdep = 0;
	dep[u] = dep[fa] + 1;
	for (auto i = head[u]; i; i = edge[i].nxt) {
		const auto v = edge[i].v;
		if (v == fa) continue;
		dfs(v, u);
		if (dep[v] > maxdep) maxdep = dep[son[u] = v];
	}
	if (!maxdep) { 
		ans[u] = 0; 
		d[u] = new vector<int>{ 1 };
		return; 
	}
	d[u] = d[son[u]];
	(*d[u]).push_back(1);
	auto utp = (*d[u]).size() - 2;
	for (auto i = head[u]; i; i = edge[i].nxt) {
		const auto v = edge[i].v;
		if (v == fa || v == son[u]) continue;
		int mtp = utp, ytp = (*d[v]).size() - 1;
		while (ytp >= 0) {
			(*d[u])[mtp] += (*d[v])[ytp];
			--mtp; --ytp;
		}
		delete d[v];
	}
	int maxd = 0;
	for (int i = utp + 1; i >= 0; --i) {
		if ((*d[u])[i] > maxd) {
			maxd = (*d[u])[i];
			ans[u] = utp - i + 1;
		}
	}
}
int n;

signed main() {
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int u, v;
		cin >> u >> v;
		addedge(u, v), addedge(v, u);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << '\n';
}