結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }