結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー alcea
提出日時 2025-07-18 22:07:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 523 ms / 3,000 ms
コード長 1,519 bytes
コンパイル時間 2,440 ms
コンパイル使用メモリ 213,596 KB
実行使用メモリ 77,308 KB
最終ジャッジ日時 2025-07-18 22:07:11
合計ジャッジ時間 9,805 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 u,v;
    cin>>u>>v;
    u--;v--;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  int par[n];
  par[0]=-1;
  vector<vector<int>> child(n);
  function<void(int,int)> dfs=[&](int cur,int from){
    for(int to:G[cur]){
      if(to==from) continue;
      par[to]=cur;
      child[cur].push_back(to);
      dfs(to,cur);
    }
  };
  dfs(0,-1);
  vector<int> dist(n);
  dist[0]=0;
  function<void(int)> dfs0=[&](int cur){
    for(int to:child[cur]){
      dist[to]=dist[cur]+1;
      dfs0(to);
    }
  };
  dfs0(0);
  vector<int> d(n);
  function<void(int)> dfs1=[&](int cur){
    for(int to:child[cur]){
      dfs1(to);
    }
    for(int to:child[cur]) d[cur]=max(d[cur],d[to]);
    d[cur]+=1;
  };
  dfs1(0);
  vector<multiset<int>> ms(n);
  function<void(int)> dfs2=[&](int cur){
    for(int to:child[cur]){
      ms[cur].insert(d[to]);
    }
    if(par[cur]!=-1){
      int p=par[cur];
      ms[p].erase(ms[p].find(d[cur]));
      //cerr<<-6;
      ms[cur].insert(1+(ms[p].size()>0?*ms[p].rbegin():0));
      ms[p].insert(d[cur]);
    }
    for(int to:child[cur]){
      dfs2(to);
    }
  };
  //cerr<<-3;
  dfs2(0);
  //cerr<<-4;
  int ans=0;
  for(int i=0;i<n;i++){
    int m=ms[i].size();
    vector<int> tmp;
    for(int key:ms[i]) tmp.push_back(key);
    sort(tmp.begin(),tmp.end());
    for(int j=0;j<m;j++){
      ans=max(ans,(m-j)*tmp[j]+1);
    }
  }
  cout<<ans<<endl;
}
0