結果

問題 No.768 Tapris and Noel play the game on Treeone
ユーザー cureskol
提出日時 2021-10-12 15:26:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 130 ms / 2,000 ms
コード長 2,081 bytes
コンパイル時間 2,009 ms
コンパイル使用メモリ 179,228 KB
実行使用メモリ 10,916 KB
最終ジャッジ日時 2024-09-17 01:30:31
合計ジャッジ時間 6,343 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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