daily 2

两道树形DP

CF 212E

我们很容易就能想到，我们搞一个无色点，然后其余两部分都一样的颜色，这样可以最大化我们的汉堡店数量，那么具体怎么枚举呢？，也很简单，就是枚举对应的根的序号，然后计算对应的子树大小，最后用01背包的思想枚举左右两个部分即可

void solve(){
  int n;
  cin>>n;
  vector<vector<int>>E(n+1);
  for(int i=0;i<n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  vector<int>dp(n+1),siz(n+1);
  function<void(int,int)>dfs=[&](int x,int f){
    siz[x]=1;
    for(int v:E[x]){
        if(v==f)continue;
        dfs(v,x);
        siz[x]+=siz[v];
    }
  };
  vector<int>ans(n+1);
  for(int i=1;i<=n;++i){
    fill(dp.begin(),dp.end(),0);
    fill(siz.begin(),siz.end(),0);
    dfs(i,-1);
    dp[0]=1;
    for(int v:E[i]){
        int size=siz[v];
        for(int vol=n;vol>=size;--vol){
            if(dp[vol-size]){
                dp[vol]=ans[vol]=1;
            }
        }
    }
  }
  int cnt=0;
  for(int i=1;i<=n-2;++i){
    if(ans[i])++cnt;
  }
  cout<<cnt<<'\n';
  for(int i=1;i<=n-2;++i){
    if(ans[i]){
        cout<<i<<' '<<(n-1-i)<<'\n';
    }
  }
  return;
}

CF 763A

另一道树形dp，我们先处理出每棵子树是不是只含有相同颜色，这是第一遍dfs，第二遍dfs，我们进行点的枚举，具体逻辑看代码，很好理解

void solve(){
  int n;
  cin>>n;
  vector<vector<int>>E(n+1);
  vector<int>c(n+1);
  for(int i=0;i<n-1;++i){
    int u,v;
    cin>>u>>v;
    E[u].push_back(v);
    E[v].push_back(u);
  }
  for(int i=1;i<=n;++i)cin>>c[i];
  vector<int>dp(n+1);
  function<void(int,int)>dfs1=[&](int x,int f){
    dp[x]=1;
    for(int v:E[x]){
        if(v==f)continue;
        dfs1(v,x);
        if(c[x]!=c[v]||dp[v]!=1){
            dp[x]=0;
        }
    }
  };
  dfs1(1,0);
  function<int(int,int,int)>dfs2=[&](int x,int f,int last){
    int cnt1=0,cnt2=0,nxt=-1;
    for(int v:E[x]){
        if(v==f)continue;
        if(dp[v]){
            ++cnt1;
            if(c[v]==c[x]){
                ++cnt2;//how many subtrees are the same color as root
            }
        }else{
            nxt=v;
        }
    }
    int siz=E[x].size();
    if(x!=1)--siz;
    if(cnt1==siz){
        return x;
    }
    if(cnt2==siz-1&&c[x]==last){
        int res=dfs2(nxt,x,c[x]);
        if(res!=-1){
            return res;
        }
    }
    return -1;
  };
  int ans=dfs2(1,0,c[1]);
  if(ans!=-1){
    cout<<"YES"<<'\n'<<ans;
  }else{
    cout<<"NO\n";
  }
  return;
}