ツリーの最小支配セットと最大独立セット

ツリーの最小支配セット:
定義1図G=(V,E)において、最小支配セットとは、Vに対して残りの点が取り出された点に対してエッジが接続されるように、Vからできるだけ少ない点を1つの集合とすることを意味する.すなわち、V‘が図Gの支配セットであるとすると、図中のいずれかの頂点uについては、集合V’に属するか、V‘の頂点に隣接するかのいずれかである.V’に任意の要素を外に出すとV‘は支配セットではなく,支配セットは極小支配セットである.Gと呼ばれるすべての支配集中頂点の個数が最も少ない支配セットを最小支配セットとし,最小支配集中頂点の個数を支配数と呼ぶ.
ここは実装部分にすぎないので、どのように使うかはテーマによって変わります.

const inf=999999999;
int dp[250][3];        //0         ，1      ，2         
vector<int>vec[250];   //    i     ，vec[i]        

void MDS_DP(int u,int fa)
{
    dp[u][0]=0;
    dp[u][1]=1;
    int inc=inf;
    int sum=0;
    bool mark=false;//        
    for(int i=0;i<vec[u].size();++i)
    {
        int j=vec[u][i];
         if(j==fa)  continue;          //       ，              ，       
         MDS_DP(j,u);
         if(dp[j][1]<=dp[j][2])
         {
             mark=true;      //       ，              （   ）    。
             sum+=dp[j][1];             //           。
         }
         else
         {
             sum+=dp[j][2];            
             inc=min(inc,dp[j][1]-dp[j][2]);  //          ，             ，         。
         }
    }
    if(mark==true)
    {
        dp[u][2]=sum;
    }
    else
    {
       if(vec[u].size()==0)
          dp[u][2]=inf;
       else
          dp[u][2]=inc+sum;     //         ，         ，       。
    }
}

ツリーの最大独立セット:
定義3図G=(V,E)にとって、最大独立セットとは、Vからできるだけ多くの点を取って集合を構成し、これらの点間にエッジが接続されないようにすることを意味する.すなわち、V’を図Gの1つの独立したセットとすると、図中の任意のエッジ(u,v)について、uとvは同時に集合V′に属することができず、uとvは共に集合V′に属さないこともできる.V'にV'要素に属さないものを追加すると、V'は独立セットではなく、V'は極めて独立セットである.Gと呼ばれるすべての頂点独立セットの頂点個数が最も多い独立セットを最大独立セットとする.
ここも実現するだけです.

vector<int>vec[250];
int dp[250][2],n;     //0      ，1     

void dfs(int v,int p)
{
    vec[v][0]=0;
    vec[v][1]=1;
    
    for(int i=0;i<n;++i)
    {
        int sz=vec[i].size();
        int u=vec[v][i];
          if(u==p)  continue;    //    
        dfs(u,v);
        
        dp[i][0]+=max(dp[u][0],dp[u][1]); //       ，       ，   。
         dp[i][1]+=dp[u][0];         //     ，     。
    }   
    
}