#35085: 第四題會TLE，能優化的都優化了，
aswendy062666@gmail.com
(Leo)
學校
:
國立臺中第二高級中學
編號 : 123466
來源 : [140.117.180.243]
最後登入時間 ：
2024-02-23 00:10:58
#include<iostream>
#include<vector>
using namespace std;
struct node{
int num = 0;
vector<int> child;
};
vector<node> position;
int ans = 0;
int dfs(node p){
int Max = 0, Sec_Max = 0, num;
for(int i = 0; i < p.num; i++)
{
num = dfs(position[p.child[i]]);
if(num > Max){
Sec_Max = Max;
Max = num;
}
else if(num > Sec_Max){
Sec_Max = num;
}
}
if(Max + Sec_Max > ans){
ans = Max + Sec_Max;
}
return Max+1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n = 0, a, b, root;
while(cin >> n){
ans = 0;
bool leaf[n] = {false};
position.resize(0);
position.resize(n);
for(int i = 0; i < n-1; i++)
{
cin >> a >> b;
position[a].child.push_back(b);
position[a].num++;
leaf[b] = true;
}
for(int i = 0; i < n; i++)
{
if(!leaf[i]){root = i; break;}
}
dfs(position[root]);
printf("%d\n", ans);
}
}
ZeroJudge Forum