結果

問題 No.3206 う し た ウ ニ 木 あ く ん 笑
ユーザー tanaka255
提出日時 2025-07-18 22:44:05
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 945 bytes
コンパイル時間 3,019 ms
コンパイル使用メモリ 283,844 KB
実行使用メモリ 43,520 KB
最終ジャッジ日時 2025-07-18 22:44:12
合計ジャッジ時間 5,860 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
int N;
vector<int>g[2<<17];
int dp[2<<17];
int dfs(int v,int prev=-1){
  dp[v]=0;
  for(int vv:g[v]){
    if(vv==prev)continue;
    dp[v]=max(dp[v],dfs(vv,v)+1);
  }
  return dp[v];
}
int ans=0;
void dfs2(int v,int prev=-1){
  vector<int>ret(g[v].size());
  rep(i,g[v].size())ret[i]=dp[g[v][i]];
  sort(ret.begin(),ret.end());
  ans=max(ans,1+(int)ret.size()*(1+ret[0]));
  int init=dp[v];
  for(int vv:g[v]){
    if(vv==prev)continue;
    if(dp[vv]==ret.back()){
      if(2<=(int)ret.size()){
        dp[v]=ret[(int)ret.size()-2]+1;
      }else{
        dp[v]=0;
      }
    }
    dfs2(vv,v);
  }
  dp[v]=init;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  cin>>N;
  rep(i,N-1){
    int u,v;cin>>u>>v,--u,--v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  dfs(0);
  //rep(i,N)cout<<dp[i]<<" \n"[i+1==N];
  dfs2(0);
  cout<<ans<<endl;
}
0