結果

問題 No.1817 Reversed Edges
コンテスト
ユーザー startcpp
提出日時 2022-01-22 02:13:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 208 ms / 2,000 ms
コード長 1,333 bytes
コンパイル時間 595 ms
コンパイル使用メモリ 69,632 KB
実行使用メモリ 15,488 KB
最終ジャッジ日時 2024-11-26 10:58:18
合計ジャッジ時間 5,291 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

//全方位木DPのお気持ちになると、pを根としたときとpの子vを根としたときの違いが、p--v辺の向きだけと分かるので、
//(vを頂点としたときの答え) = (pを頂点としたときの答え) + (p-->vが順張りなら+1, 逆張りなら-1) と分かる。
//よって頂点0を頂点としたときの答えを求めておき、上記の漸化式でもう一度 dfs をすればよい。
//このように、部分木に関する探索をおこなったあと、根に関する探索をおこなう手法を「全方位木DP」と呼ぶ。
#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> 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;
}
0