USACO銀牌題目 CSES1131 Tree Diameter (DFS Tree) 代碼
2022-08-30 19:29 作者:信奧賽USACO鄭老師 | 我要投稿
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN=2e5+1;
vector<int> tree[MN];
int diameter=0;
int vis[MN];
?
int dfs(int x){
? ? vis[x]=1;
? ? int l1=-1,l2=-1;
? ? for(auto y : tree[x]){
? ? ? ? if(vis[y]==0){
? ? ? ? ? ? int t=dfs(y);
? ? ? ? ? ? if(t>l1){
? ? ? ? ? ? ? ? l2=l1;
? ? ? ? ? ? ? ? l1=t;
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? if(t>l2){
? ? ? ? ? ? ? ? ? ? l2=t;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? diameter=max(diameter,l1+l2+2);
? ? return l1+1;
}? ??
? ??
?
int main()
{
? ? int n,a,b;
? ? cin>>n;
? ? for(int i=0;i<n-1;i++){
? ? ? ? cin>>a>>b;
? ? ? ? tree[a].push_back(b);
? ? ? ? tree[b].push_back(a);
? ? }
? ? dfs(1);
? ? cout<<diameter<<endl;? ? ? ??
? ? return 0;
}
標(biāo)簽: