1 solutions

  • 0
    @ 2025-3-9 21:39:53
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    typedef multiset<ll>::iterator itt;
    const int N = 5e5+11, P = 998244353;
    
    int n;
    ll f[N], ans;
    int tot, head[N], ver[N], nex[N];
    
    void add(int x, int y){
    	nex[++tot] = head[x];
    	head[x] = tot;
    	ver[tot] = y;
    }
    
    void dfs(int x, int fa){
    	ll cnt = 0;
    	for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){
    		int y = ver[i];
    		cnt ++; dfs(y, x);
    	} if(!cnt) {f[x] = 0; return ;} 
    	
    	
    	for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){
    		f[x] = max(f[x], max(1ll, f[ver[i]]) + cnt - 1);
    	} ans = max(ans, f[x] + (fa ? 1 : 0));
    	
    	if(cnt < 2) return;
    	ll q[cnt+11], t = 0;
    	for(int i=head[x]; i; i=nex[i]) if(ver[i] != fa){
    		q[t++] = f[ver[i]];
    	}
    	sort(q, q + t);
    	ans = max(ans, q[t-1] + q[t-2] + cnt - 2 + (fa ? 1 : 0));
    }
    
    void work(){
    	scanf("%d",&n);
    	tot = 0, ans = 1;
    	for(int i=1;i<=n;i++) f[i] = head[i] = 0;
    	for(int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y), add(x, y), add(y, x);
    	dfs(1, 0); 
    //	printf("ans=%lld\n",ans);
    	printf("%lld\n",ans);	
    }
    
    int main(){
    	int t = 1; scanf("%d",&t);
    	while(t--) work(); return 0;
    }
    
    • 1

    Information

    ID
    531
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    # Submissions
    10
    Accepted
    1
    Uploaded By