CF1926G Vlad and Trouble at MIT

题意

有一棵树，树上每个节点有\(C\) , \(S\) , \(P\) 三种，现在可以选择一些边断掉，使得每个连通块内没有同时出现 \(S\) , \(P\) 的情况，问最少断多少条

思路

板子树形 \(DP\)

考虑 \(dp_{i,0/1,0/1}\) 表示以 \(i\) 为子树，是否有跟 \(i\) 联通的 \(S\) 和 \(P\)

转移

 dp[x][0][0]+=min({dp[i][0][0],dp[i][0][1]+1,dp[i][1][0]+1});
 dp[x][1][0]+=min({dp[i][0][0],dp[i][1][0],dp[i][0][1]+1});
 dp[x][0][1]+=min({dp[i][0][0],dp[i][1][0]+1,dp[i][0][1]});

对每种情况分类讨论即可

需要注意判断 \(i\) 节点是否为 \(S\) , \(P\) , 以免状态不合法，不合法状态设为 \(+ \inf\)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
vector<int> g[N];
char s[N];
int dp[N][2][2];
void dfs(int x)
{
    for(auto i:g[x])
    {
        dfs(i);
        dp[x][0][0]+=min({dp[i][0][0],dp[i][0][1]+1,dp[i][1][0]+1});
        dp[x][1][0]+=min({dp[i][0][0],dp[i][1][0],dp[i][0][1]+1});
        dp[x][0][1]+=min({dp[i][0][0],dp[i][1][0]+1,dp[i][0][1]});
    }
    if(s[x]=='P') dp[x][0][0]=dp[x][0][1]=1e9;
    if(s[x]=='S') dp[x][0][0]=dp[x][1][0]=1e9;
}
int main()
{
    int cas;
    cin>>cas;
    while(cas--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) dp[i][0][0]=dp[i][1][0]=dp[i][0][1]=0,g[i].clear();
        for(int i=2;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            g[x].push_back(i);
        } 
        scanf("%s",s+1);
        dfs(1);
        cout<<min({dp[1][0][0],dp[1][0][1],dp[1][1][0]})<<"\n";
    }
}