我這題這樣寫TLE
#include <bits/stdc++.h> using namespace std; int ans=0; int Count(int target,vector<vector<int>>& tree,vector<int>& high){ if(high[target]){ return high[target]; } if(tree[target].empty()){ return 1; } int max_1=0; int max_2=0; for(int i:tree[target]){ if(Count(i,tree,high)>max_2){ max_2=Count(i,tree,high); if(max_2>max_1){ swap(max_2,max_1); } } } high[target] = max_1+1; ans = max(max_1+max_2,ans); return high[target]; } main() { ios::sync_with_stdio(0); cin.tie(0); while(1){ int n; cin>>n; vector<vector<int>> tree(n); vector<int> high(n); int a,b; for(int i=0;i<n-1;i++){ cin>>a>>b; tree[a].push_back(b); } for(int i=0;i<n;i++){ if(!high[i]){ Count(i,tree,high); } } cout<<ans<<"\n"; ans=0; } return 0; }
但我把cin擺到while裡就過了,如下
#include <bits/stdc++.h> using namespace std; int ans=0; int Count(int target,vector<vector<int>>& tree,vector<int>& high){ if(high[target]){ return high[target]; } if(tree[target].empty()){ return 1; } int max_1=0; int max_2=0; for(int i:tree[target]){ if(Count(i,tree,high)>max_2){ max_2=Count(i,tree,high); if(max_2>max_1){ swap(max_2,max_1); } } } high[target] = max_1+1; ans = max(max_1+max_2,ans); return high[target]; } main() { ios::sync_with_stdio(0); cin.tie(0); int n; while(cin>>n){ vector<vector<int>> tree(n); vector<int> high(n); int a,b; for(int i=0;i<n-1;i++){ cin>>a>>b; tree[a].push_back(b); } for(int i=0;i<n;i++){ if(!high[i]){ Count(i,tree,high); } } cout<<ans<<"\n"; ans=0; } return 0; }