這道題題意是:
從根節(jié)點(diǎn)出發(fā)，每條邊僅僅走一遍，每個(gè)節(jié)點(diǎn)僅僅走一遍，問(wèn)遍歷完整棵樹然后回到根需要加多少條邊。
這題的本質(zhì)是在樹的路徑最小劃分。可以使用樹形DP
狀態(tài)dp[pos][0]表示遍歷完這顆子樹并且鏈的一端在根節(jié)點(diǎn)最少需要添加邊的數(shù)量
dp[pos][1]表示完遍歷這顆子樹需要添加最少的邊的數(shù)量
然后下面狀態(tài)轉(zhuǎn)移就簡(jiǎn)單了
son[pos]=dp[i][1]，i為父節(jié)點(diǎn)為pos的子樹
num[pos]為以pos為根節(jié)點(diǎn)的子樹數(shù)量
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