結果

問題 No.1752 Up-Down Tree
ユーザー harurun
提出日時 2021-11-19 23:23:21
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,300 bytes
コンパイル時間 1,370 ms
コンパイル使用メモリ 106,688 KB
最終ジャッジ日時 2025-01-25 20:57:50
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 7 WA * 9 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <deque>
#include <utility>
#include <queue>
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;
    G[A-1].push_back(B-1);
    G[B-1].push_back(A-1);
  }
  deque<pair<int,int>> dq;
  dq.push_back(make_pair(0,0));
  vector<int> depth(N,-1);
  while(!dq.empty()){
    pair<int,int> q=dq.back();dq.pop_back();
    depth[q.first]=q.second;
    for(int to:G[q.first]){
      if(depth[to]==-1){
        dq.push_back(make_pair(to,q.second+1));
      }
    }
  }
  // cerr<<"depth"<<endl;
  // for(int i=0;i<N;i++){
  //   cerr<<depth[i]<<" ";
  // }cerr<<endl;
  vector<int> parent(N);
  parent[0]=-1;
  vector<vector<int>> children(N);
  priority_queue<pair<int,int>> pq;
  for(int i=0;i<N;i++){
    for(int to:G[i]){
      if(depth[i]<depth[to]){
        //cerr<<"c "<<i<<" "<<to<<endl;
        children[i].push_back(to);
      }else{
        //cerr<<"p "<<i<<" "<<to<<endl;
        parent[i]=to;
      }
    }
    if(children[i].empty()){
      pq.push(make_pair(depth[i],i));
    }
  }
  // for(int i=0;i<N;i++){
  //   cerr<<parent[i]<<" ";
  // }cerr<<endl;
  vector<int> num(N,1);
  while(!pq.empty()){
    pair<int,int> q=pq.top();
    pq.pop();
    int point=q.second;
    
    int par=parent[point];
    if(par==-1){
      break;
    }
    if(num[par]!=1){
      continue;
    }
    if(children[par].size()<=2){
      //cerr<<"par:"<<par<<endl;
      for(int i:children[par]){
        num[par]+=num[i];
        //cerr<<i<<" "<<num[i]<<endl;
      }//cerr<<endl;
    }else{
      vector<pair<int,int>> cnt;
      for(int i:children[par]){
        cnt.push_back(make_pair(num[i],i));
      }
      sort(cnt.rbegin(),cnt.rend());
      num[par]+=cnt[0].first+cnt[1].first;
      if(parent[par]!=-1){
        for(int i=2;i<cnt.size();i++){
          parent[cnt[i].second]=parent[par];
          children[parent[par]].push_back(cnt[i].second); 
        }
      }
    }
    pq.push(make_pair(depth[par],par));
  }
  // for(int i=0;i<N;i++){
  //   for(auto j:children[i]){
  //     cerr<<i<<" "<<j<<endl;
  //   }
  // }
  // for(int i=0;i<N;i++){
  //   cerr<<num[i]<<" ";
  // }cerr<<endl;
  cout<<num[0]<<endl;
  return 0;
}
0