一开始要符合题目条件， 那么肯定没有任何一个点是孤立的， 也就是说没有点的度数是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<cstdio>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 112345;
vector<int> g[MAXN], leaf;
vector<pair<int, int> > 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;
} 不好想