题意：
有一棵树，现在想把它组装成环，问最少的步数是多少？
思路：
如果想成为环，那么首先思考当一个节点的直接连接的儿子数量大于1的时候就要把它儿子分开了，比如
1节点有四个直接相连的儿子那么，若其想度为2的话只能有两个线存在，统一选择把与父亲节点相连的分开，cost = 1，然后把儿子节点大于2个的都分开，cost = 2，但是儿子分开之后还是要连起来的，与父亲连成一条链，cost = 2，从的 cost=2∗（大于2的儿子部分）+1=5 ，到这里1、2、3、4、5已经成为一条链了，但是这条游离的链还要与根节点相连所以要加1即非根结点： cost=2∗（大于2的儿子部分）+2
若大于2的儿子部分 = son，则： (非根节点)cost=2∗(son−2)+2=2∗(son−1) ,对于根节点其实就不用和它的根相连和分离接了所以 cost=2∗(son−2) ，这里最后算出的结果是一条链，所以需要加1.
#include <iostream> #include <cstdio> #include <cstring> using namespace std; inline int read() { char k = 0,ls; ls=getchar(); for(;ls<'0'||ls>'9';k = ls,ls = getchar()); int x=0; for(;ls >= '0' && ls <= '9';ls = getchar()) x=x*10+ls-'0'; if(k == '-') x=0-x; return x; } const int maxn = 1000005; int n; int head[maxn]; int vis[maxn]; int pos,ans; struct { int e; int next; }edge[maxn*2]; int dfs(int u) { vis[u] = true; int son = 0; for(int i = head[u];i != -1; i = edge[i].next) { int to = edge[i].e; if(vis[to]) continue; son += dfs(to); } if(son > 1) { if(u == 1) { ans += 2*(son - 2); } else { ans += 2*(son - 1); } return false; } else return true; } int main(int argc, char const *argv[]) { //freopen("in.txt","r",stdin); int tt; tt = read(); while(tt--) { scanf("%d",&n); memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); ans = pos = 0; for(int i = 1;i < n; i++) { int a,b; a = read(),b = read(); edge[pos].e = b; edge[pos].next = head[a]; head[a] = pos++; edge[pos].e = a; edge[pos].next = head[b]; head[b] = pos++; } dfs(1); printf("%d\n",ans+1); } return 0; }