这道题题意是:
从根节点出发，每条边仅仅走一遍，每个节点仅仅走一遍，问遍历完整棵树然后回到根需要加多少条边。
这题的本质是在树的路径最小划分。可以使用树形DP
状态dp[pos][0]表示遍历完这颗子树并且链的一端在根节点最少需要添加边的数量
dp[pos][1]表示完遍历这颗子树需要添加最少的边的数量
然后下面状态转移就简单了
son[pos]=dp[i][1]，i为父节点为pos的子树
num[pos]为以pos为根节点的子树数量
dp[pos][0]=min(son[pos]+dp[i][0]-dp[i][1]+num[pos]-1),i为以pos为根的子树
dp[pos][1]=min(son[pos]+dp[i][0]-dp[i][1]+dp[j][0]-dp[j][1]+num[pos]-2),i为以pos为根的子树
1 # include <stdio.h>
2 # include <string.h>
3 # include <stdlib.h>
4 # define N 110000
5 # define M 210000
6 int g[N],n,tmp[N];
7 int nxt[M],v[M],c=0;
8 int dp[N][2];
9 void solve(int pos,int fa)
10 {
11 if(dp[pos][0]!=-1) return;
12 else
13 {
14 int null=0,p,total=0,num=0,min1=0xfffffff,min2=0xfffffff;
15 for(p=g[pos];p!=-1;p=nxt[p])
16 if(v[p]!=fa)
17 {
18 null=1;
19 solve(v[p],pos);
20 if(dp[v[p]][0]-dp[v[p]][1]<min1)
21 {
22 min2=min1;
23 min1=dp[v[p]][0]-dp[v[p]][1];
24 }
25 else if(dp[v[p]][0]-dp[v[p]][1]<min2)
26 {
27 min2=dp[v[p]][0]-dp[v[p]][1];
28 }
29 total+=dp[v[p]][1];
30 num++;
31 }
32 if(!null)
33 dp[pos][0]=dp[pos][1]=0;
34 else
35 {
36 dp[pos][0]=total+min1+num-1;
37 if(min2!=0xfffffff)
38 dp[pos][1]=total+min1+min2+num-2;
39 if(dp[pos][0]<dp[pos][1]||dp[pos][1]==-1)
40 dp[pos][1]=dp[pos][0];
41 }
42 }
43 }
44 int main()
45 {
46 int i;
47 scanf("%d",&n);
48 memset(g,-1,sizeof(g));
49 c=0;
50 for(i=1;i<n;i++)
51 {
52 int a,b;
53 scanf("%d%d",&a,&b);
54 v[c]=b;
55 nxt[c]=g[a];
56 g[a]=c++;
57 v[c]=a;
58 nxt[c]=g[b];
59 g[b]=c++;
60 }
61 memset(dp,-1,sizeof(dp));
62 solve(1,0);
63 printf("%d\n",dp[1][1]+1);
64 return 0;
65 }
66