//全方位木DPのお気持ちになると、pを根としたときとpの子vを根としたときの違いが、p--v辺の向きだけと分かるので、 //(vを頂点としたときの答え) = (pを頂点としたときの答え) + (p-->vが順張りなら+1, 逆張りなら-1) と分かる。 //よって頂点0を頂点としたときの答えを求めておき、上記の漸化式でもう一度 dfs をすればよい。 //このように、部分木に関する探索をおこなったあと、根に関する探索をおこなう手法を「全方位木DP」と呼ぶ。 #include #include using namespace std; int n; vector et[100000]; int ans[100000]; int dfs(int p, int v) { int ret = 0; for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (nv == p) continue; if (v > nv) ret++; ret += dfs(v, nv); } return ret; } void dfs2(int p, int v, int ans_v) { ans[v] = ans_v; for (int i = 0; i < et[v].size(); i++) { int nv = et[v][i]; if (nv == p) continue; dfs2(v, nv, ans_v + ((v < nv) ? 1 : -1)); } } int main() { int i; cin >> n; for (i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; et[a].push_back(b); et[b].push_back(a); } int res = dfs(0, 0); dfs2(0, 0, res); for (i = 0; i < n; i++) { cout << ans[i] << endl; } return 0; }