一开始要符合题目条件， 那么肯定没有任何一个点是孤立的， 也就是说没有点的度数是1

所以我就想让度数是1的叶子节点相互连起来。然后WA

然后看这哥们的博客

https://blog.csdn.net/trote_w/article/details/79504280

原来连叶子的时候， 有三个叶子的时候， 中间的留到下一次连，左右连起来。

我之前是直接按照顺序连。

按照顺序那么边可能会封闭在一颗子树里面， 比如一颗子树有两个叶子 ，然后他们互相连接。

这个时候把 子树的根 和 子树的根的父亲连的边切断， 这一颗子树就分离出来了， 就不联通了。

如果是中间留下连两边的话， 这样可以保证当前子树添加的边不是封闭的， 是可以有边连到

外面去的， 也就是说可以从当前子树的叶子连接到其他子树的叶子上， 这样即使把子树的根 和 子树的根的父亲连的边切断

还是有边连出去的， 就不会不联通了。

这样三个三个一组来连， 然后到最后有三种情况。

因为前面已经连完了， 就可以等价于只剩下树根和剩下的叶子节点。

也就是说可以看成一个根节点下连着0~2个叶子。

以下讨论都看成是这样， 那么就很好想了。

（1）叶子数是三的倍数， 刚好连完。这个时候就over了， 可以输出答案了。

（2）叶子数是三的倍数+1， 也就是最后剩下一个叶子， 那么把这个叶子和树根连接。

（3）叶子数是三的倍数加2， 也就是说剩下两个叶子， 那么把两个叶子互相连接。

另外UVa 1670数据有问题， 去Uvalive 5920提交

#include
    
     #include
     
      #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 112345;vector
      
        g[MAXN], leaf;vector
       
        
          > ans;int n, root;int dfs(int u, int fa){	REP(i, 0, g[u].size())	{		if(g[u][i] == fa) continue;		dfs(g[u][i], u);	}		if(g[u].size() == 1) //叶子节点 	{		leaf.push_back(u);		if(leaf.size() == 3) //左右连， 中间留下 		{			int t = leaf[1];			ans.push_back(make_pair(leaf[0], leaf[2]));			leaf.clear();			leaf.push_back(t);		}	}}int main(){	while(~scanf("%d", &n))	{		REP(i, 1, n + 1) g[i].clear();		REP(i, 0, n - 1) 		{			int u, v;			scanf("%d%d", &u, &v);			g[u].push_back(v); g[v].push_back(u);				if(g[u].size() > 1) root = u; //找度数大于1的做树根 			if(g[v].size() > 1) root = v;		}					leaf.clear(); ans.clear();		dfs(root, -1);				if(leaf.size() == 2) ans.push_back(make_pair(leaf[0], leaf[1])); //最后剩下的节点，见前面的解析。 		else if(leaf.size() == 1) ans.push_back(make_pair(root, leaf[0]));				printf("%d\n", ans.size());		REP(i, 0, ans.size()) printf("%d %d\n", ans[i].first, ans[i].second);	}		return 0;	}
        
       
      
     
    

不好想