树+dfs

原题链接：https://codeforces.com/problemset/problem/2050/G
题解链接：https://blog.csdn.net/Lazy_ChessPlayer/article/details/144279298

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define INF 2e9
using namespace std;
#define lowbit(x) x&(-x)
#define endl '\n'
using ll = long long;
using pii = pair<ll,ll>;
const double PI = acos(-1);
const int N=2e5+10;
vector<int> g[N*2];
int val[N];
int du[N];
ll ans=0;
int dfs(int u,int fa){
	vector<int> res;
	for(auto t:g[u]){
		if(t==fa) continue;
		int m=dfs(t,u);
		if(m>0) res.push_back(m);
	}
	sort(res.begin(),res.end(),greater<int>());
	int now=val[u];
	if(!res.empty()){
		now+=res[0];
	}
	ans=max(ans,(ll)now);
	if(res.size()>=2){
		ans=max(ans,(ll)(val[u]+res[0]+res[1]));
	}
	return now;
}
void solve(){
	ans=-0x3f3f3f;
	int n;cin>>n;
	for(int i=1;i<=n;i++){
		g[i].clear();
		du[i]=0;
		val[i]=0;
	}
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		du[u]++;
		du[v]++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		val[i]=du[i]-2;
	}
	dfs(1,0);
	cout<<ans+2<<endl;
}


int main() {
	
//	ios::sync_with_stdio(false);
//	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}