原题链接

题解

1.添加几条边，使得对于任意节点，都有环存在，且所在最小环的大小皆大于3
2.看成有中心点的散发图，最优添加情况为叶子节点相连
3.如果两个叶子节点的父节点为lca，那么这两个叶子节点不能直接相连
4.看成若干个菊花，每朵菊花的花瓣都是叶子节点，同一朵花上的花瓣不能直接相连，所有叶子节点都要有边往外连，求问最少需要几条边
5.这让我想到了cf上的一道题，相邻的不同字母可以消除，求问最后还剩下几个字母？

code

#include<bits/stdc++.h>
using namespace std;
int u[100005]={0},v[100005]={0},du[100005]={0};
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        memset(du,0,sizeof du);
        for(int i=1;i<n;i++)
        {
            cin>>u[i]>>v[i];
            du[u[i]]++;
            du[v[i]]++;
        }
        if(n<=3)
        {
            puts("-1");
            continue;
        }
        map<int,int> q;
        int leaf=0;
        for(int i=1;i<n;i++)
        {
            if(du[u[i]]==1)q[v[i]]++,leaf++;
            if(du[v[i]]==1)q[u[i]]++,leaf++;
        }
        if(q.size()==1)
        {
            puts("-1");
            continue;
        }
        int  ans=0;
        for(auto it=q.begin();it!=q.end();it++)
        {
            ans=max(ans,it->second);
        }
        cout<<((ans>leaf/2)?ans:(leaf+1)/2)<<endl;
    }
    return 0;
}