結果
問題 | No.1817 Reversed Edges |
ユーザー |
|
提出日時 | 2022-01-21 21:56:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 1,002 bytes |
コンパイル時間 | 2,226 ms |
コンパイル使用メモリ | 200,364 KB |
最終ジャッジ日時 | 2025-01-27 13:42:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int N; cin >> N; vector<vector<int>> G(N); for(int i = 0; i < N - 1; i++){ int a, b; cin >> a>> b; a--; b--; G[a].push_back(b); G[b].push_back(a); } vector<int> dp(N); auto dfs = [&](auto dfs, int now, int par = -1)->void{ for(int to : G[now]){ if(to == par) continue; dfs(dfs, to, now); dp[now] += dp[to]; if(now > to) dp[now]++; } }; dfs(dfs, 0); auto dfs2 = [&](auto dfs2, int now, int temp, int par = -1)->void{ dp[now] += temp; for(int to : G[now]){ if(to == par) continue; if(now > to){ dfs2(dfs2, to, dp[now] - dp[to] - 1, now); } else{ dfs2(dfs2, to, dp[now] - dp[to] + 1, now); } } }; dfs2(dfs2, 0, 0); for(int i = 0; i < N; i++) cout << dp[i] << endl; }