結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー tau1235
提出日時 2025-07-18 22:50:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 395 ms / 3,000 ms
コード長 1,572 bytes
コンパイル時間 3,108 ms
コンパイル使用メモリ 289,244 KB
実行使用メモリ 53,976 KB
最終ジャッジ日時 2025-07-18 22:50:25
合計ジャッジ時間 8,569 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int merge(int a,int b){return max(a,b);}
int apply(int a){return a+1;}
int e(){return 0;}
template <typename T,T (*merge)(T,T),T (*apply)(T),T (*e)()>
struct ReRooting{
  vector<vector<int>> g;
  vector<vector<T>> dp;
  vector<T> ans;

  ReRooting(int n):g(n),dp(n),ans(n){}

  void add_edge(int v,int u){
    g[v].push_back(u);
    g[u].push_back(v);
  }

  void build(){
    dfs(0);
    dfs2(0);
  }

  T dfs(int v,int p=-1){
    dp[v].resize(g[v].size());
    T ret=e();
    for (int i=0;i<g[v].size();i++){
      int u=g[v][i];
      if (u==p) continue;
      dp[v][i]=dfs(u,v);
      ret=merge(ret,dp[v][i]);
    }
    return apply(ret);
  }

  void dfs2(int v,T dp_p=1,int p=-1){
    vector<T> dpr(g[v].size()+1);
    dpr[g[v].size()]=e();
    for (int i=g[v].size()-1;i>=0;i--){
      int u=g[v][i];
      if (u==p) dp[v][i]=dp_p;
      dpr[i]=merge(dpr[i+1],dp[v][i]);
    }
    T dpl=e();
    for (int i=0;i<g[v].size();i++){
      int u=g[v][i];
      if (u!=p) dfs2(u,apply(merge(dpl,dpr[i+1])),v);
      dpl=merge(dpl,dp[v][i]);
    }
    ans[v]=apply(dpl);
  }
};

int main(){
  int n;
  cin>>n;
  ReRooting<int,merge,apply,e> g(n);
  for (int i=0;i<n-1;i++){
    int u,v;
    cin>>u>>v;
    u--;v--;
    g.add_edge(u,v);
  }
  g.build();
  int ans=0;
  for (int i=0;i<n;i++){
    auto vec=g.dp[i];
    int m=vec.size();
    sort(vec.begin(),vec.end());
    for (int j=0;j<m;j++){
      int k=lower_bound(vec.begin(),vec.end(),vec[j])-vec.begin();
      ans=max(ans,vec[j]*(m-k)+1);
    }
  }
  cout<<ans<<endl;
}
0