Cable Protection

题目大意：求一颗基环树的最小点覆盖。

题解：其实是一道比较板子的树形dp，dp[i][0/1]表示取或者不取i点的最小点。但是首先我们要把基环树断开，然后分别考虑a被覆盖和b被覆盖的情况。

dp[i][0]=∑min(dp[j][0],dp[j][1])

d p [ i ] [ 1 ] = ∑ d p [ j ] [ 0 ]

AC_code:

 1 int dp[maxn][3];
 2 int a,b,flag;
 3 vector<int>g[maxn];
 4 void dfs(int x,int fa){
 5     dp[x][0]=dp[x][1]=0;
 6     for(int i=0;i<g[x].size();i++){
 7         int v=g[x][i];
 8         if(fa==v) continue;
 9         dfs(v,x);
10         dp[x][0]+=min(dp[v][0],dp[v][1]);
11         dp[x][1]+=dp[v][0];
12     }
13     dp[x][0]++;
14     if(x==b&&flag==2) dp[x][1]=dp[x][0];
15 }
16 void run(){
17     int n=rd(),m=rd();
18     rep(i,1,n+m){
19         int x=rd(),y=rd();
20         if(!flag&&x<n&&y<n){
21             a=x,b=y;
22             flag=1;
23             continue;
24         }
25         g[x].push_back(y);
26         g[y].push_back(x);
27     }
28     int ans=inf;
29     flag=1;
30     dfs(a,-1);
31     ans=min(dp[a][0],ans);
32     flag=2;
33     dfs(a,-1);
34     ans=min(ans,min(dp[a][0],dp[a][1]));
35     printf("%d
",ans);
36 }