結果

問題 No.768 Tapris and Noel play the game on Treeone
ユーザー cureskolcureskol
提出日時 2021-10-12 15:26:18
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 101 ms / 2,000 ms
コード長 2,081 bytes
コンパイル時間 1,750 ms
コンパイル使用メモリ 180,476 KB
実行使用メモリ 11,032 KB
最終ジャッジ日時 2023-10-17 02:56:28
合計ジャッジ時間 7,064 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 70 ms
7,584 KB
testcase_08 AC 30 ms
5,652 KB
testcase_09 AC 36 ms
6,080 KB
testcase_10 AC 27 ms
5,476 KB
testcase_11 AC 94 ms
9,900 KB
testcase_12 AC 99 ms
9,944 KB
testcase_13 AC 93 ms
9,772 KB
testcase_14 AC 90 ms
9,736 KB
testcase_15 AC 96 ms
10,196 KB
testcase_16 AC 99 ms
10,196 KB
testcase_17 AC 101 ms
10,292 KB
testcase_18 AC 92 ms
11,032 KB
testcase_19 AC 90 ms
10,792 KB
testcase_20 AC 92 ms
10,640 KB
testcase_21 AC 86 ms
10,212 KB
20evil_special_uni1.txt AC 98 ms
10,196 KB
20evil_special_uni2.txt AC 94 ms
9,932 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=(n-1);i>=0;i--)
#define ALL(v) v.begin(),v.end()

//key_t:辺固有の情報　頂点固有の情報はラムダの方でキャプチャさせる
//sum_t:計算結果
template<typename key_t,typename sum_t=key_t>
struct ReRooting{
  struct Edge {
    int from,to;
    key_t cost;
    sum_t dp1,dp2;
    //dp1:部分木の内容
    //dp2:e=g[idx][i]の時、g[idx][0,i)のdp1の累積が入る
  };
  using S=function<sum_t(sum_t,Edge)>;
  using M=function<sum_t(sum_t,sum_t)>;

  vector<vector<Edge>> g;
  const S score;
  const M merge;
  const sum_t id;
  vector<sum_t> dp1,dp2;
  ReRooting(int n,const S &score,const M &merge,const sum_t &id=sum_t{})
    :g(n),score(score),merge(merge),id(id),dp1(n,id),dp2(n,id){}

  void add_edge(int u,int v,const key_t &c){
    g[u].emplace_back(Edge{u,v,c,id,id});
    g[v].emplace_back(Edge{v,u,c,id,id});
  }
  void add_directed_edge(int u,int v,const key_t &c){
    g[u].emplace_back(Edge{u,v,c,id,id});
  }

  void dfs1(int idx,int pre){
    for(auto &e:g[idx])if(e.to!=pre){
      dfs1(e.to,idx);
      e.dp1=score(dp1[e.to],e);
      dp1[idx]=merge(dp1[idx],e.dp1);
    }
  }

  void dfs2(int idx,int pre,sum_t top){
    sum_t now=id;
    for(auto &e:g[idx]){
      e.dp2=now;
      if(e.to==pre)e.dp1=score(top,e);
      now=merge(now,e.dp1);
    }
    dp2[idx]=now;
    now=id;
    reverse(g[idx].begin(),g[idx].end());
    for(auto &e:g[idx]){
      if(e.to!=pre)
        dfs2(e.to,idx,merge(e.dp2,now));
      now=merge(now,e.dp1);
    }
  }

  vector<sum_t> build(){
    dfs1(0,-1);
    dfs2(0,-1,id);
    return dp2;
  }
};

int main(){
  int n;cin>>n;
  auto score=[](bool x,auto e){
    return !x;
  };
  auto merge=[](bool x,bool y){
    return x&y;
  };
  ReRooting<bool> g(n,score,merge,1);
  REP(_,n-1){
    int u,v;cin>>u>>v;u--;v--;
    g.add_edge(u,v,0);
  }
  auto ans=g.build();
  vector<int> fans;
  REP(i,n)if(ans[i])fans.push_back(i);
  cout<<fans.size()<<'\n';
  for(int p:fans)cout<<p+1<<'\n';
}
0