結果

問題 No.1817 Reversed Edges
ユーザー startcppstartcpp
提出日時 2022-01-22 02:13:11
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 221 ms / 2,000 ms
コード長 1,333 bytes
コンパイル時間 688 ms
コンパイル使用メモリ 69,504 KB
実行使用メモリ 15,616 KB
最終ジャッジ日時 2024-05-04 20:43:50
合計ジャッジ時間 5,239 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,760 KB
testcase_01 AC 3 ms
5,760 KB
testcase_02 AC 3 ms
5,760 KB
testcase_03 AC 2 ms
5,760 KB
testcase_04 AC 2 ms
5,888 KB
testcase_05 AC 2 ms
5,888 KB
testcase_06 AC 2 ms
5,888 KB
testcase_07 AC 169 ms
8,960 KB
testcase_08 AC 82 ms
7,296 KB
testcase_09 AC 156 ms
8,840 KB
testcase_10 AC 93 ms
7,552 KB
testcase_11 AC 119 ms
8,192 KB
testcase_12 AC 193 ms
9,472 KB
testcase_13 AC 195 ms
9,472 KB
testcase_14 AC 221 ms
9,472 KB
testcase_15 AC 191 ms
9,408 KB
testcase_16 AC 188 ms
9,472 KB
testcase_17 AC 187 ms
9,472 KB
testcase_18 AC 186 ms
9,472 KB
testcase_19 AC 196 ms
9,472 KB
testcase_20 AC 200 ms
9,284 KB
testcase_21 AC 194 ms
9,472 KB
testcase_22 AC 170 ms
9,468 KB
testcase_23 AC 164 ms
9,472 KB
testcase_24 AC 181 ms
15,616 KB
権限があれば一括ダウンロードができます

ソースコード

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