题目大意：求一颗基环树的最小点覆盖。
题解：其实是一道比较板子的树形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\n",ans); 36 }
原文：https://www.cnblogs.com/zpj61/p/14532475.html