結果
問題 | No.768 Tapris and Noel play the game on Treeone |
ユーザー |
![]() |
提出日時 | 2019-03-28 15:26:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 213 ms / 2,000 ms |
コード長 | 904 bytes |
コンパイル時間 | 1,641 ms |
コンパイル使用メモリ | 170,548 KB |
実行使用メモリ | 10,160 KB |
最終ジャッジ日時 | 2024-10-12 23:03:18 |
合計ジャッジ時間 | 6,985 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
#include <bits/stdc++.h>using namespace std;int N;vector<int> G[100010];int dp[100010];int dp2[100010];bool ans[100010];void dfs(int u, int p) {dp[u] = 1;for(int v : G[u]) {if(v == p) continue;dfs(v, u);dp[u] &= !dp[v];}}void dfs2(int u, int p, int carryin) {dp2[u] = 0;for(int v : G[u]) {if(v == p) dp2[u] += !carryin;else dp2[u] += !dp[v];}//cout<<u<<" "<<dp[u]<<" "<<G[u].size()<<endl;if(dp2[u] == G[u].size()) ans[u] = true;for(int v : G[u]) {if(v == p) continue;dfs2(v, u, dp2[u]-!dp[v]==G[u].size()-1);}}int main() {cin >> 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);}dfs(0, -1);dfs2(0, -1, 0);cout << count(ans, ans+N, true) << endl;for(int i = 0; i < N; ++i) {if(ans[i]) cout << i+1 << endl;}return 0;}