CF 461B - 트리 DP(Appleman and Tree)

제목: 나무 한 그루를 제시한다. 각 점은 검은색이거나 흰색이거나 검은 점의 수량은 k이다. 나무를 k자 나무로 나누고 각 자 나무는 검은 점만 있는 구분 방안을 구한다.
사고방식: 나무 dp는 여전히 보기 좋다. 한 노드 u에 대해 말하자면 그것이 검은 점이라면 그 나무에 검은 점을 포함하는 모든 하위 나무를 삭제해야 한다. 그렇지 않으면 검은 점을 삭제해야 하지만 검은 점을 포함하는 하위 나무를 보존할 수 있다.dp[u]는 u를 처리한 하위 트리의 총 방안 수를 표시하고,del[u]는 u의 하위 트리에 검은 점을 포함하는 하위 트리를 모두 삭제하는 방안 수를 나타낸다.그러면 분명히 u의 아들 v가 대표하는 자수를 삭제하는 총 방안수는 dp[v]+del[v]이다. 즉, v의 자수를 삭제하거나 u-v의 가장자리를 삭제한다.다음에 상황에 따라 토론을 하면 됩니다. 만약에 u의 검은 점이 결과가 계산이 좋으면 그렇지 않으면 아들 v가 대표하는 하위 나무에 대해 현재의 것을 보류하든지 이전에 방문한 것을 보류하든지 두 가지 방안의 수를 합치면 됩니다.
코드:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn = 100000+10;
const int mod = 1000000007;
struct Edge
{
    int v,next;
    Edge(int v = 0,int next = 0):v(v),next(next){}
}edges[maxn<<2];
int head[maxn],color[maxn],tcol[maxn],nEdge;
void AddEdges(int u,int v)
{
    edges[++nEdge] = Edge(v,head[u]);
    head[u] = nEdge;
    edges[++nEdge] = Edge(u,head[v]);
    head[v] = nEdge;
}
ll dp[maxn],del[maxn];
void dfs(int u,int fa)
{
    if(color[u])
    {
        dp[u] = 1;
        del[u] = 0;
        tcol[u] = 1;
    }
    else
    {
        dp[u] = 0;
        del[u] = 1;
        tcol[u] = 0;
    }
    for(int k = head[u];k!=-1;k=edges[k].next)
    {
        int v = edges[k].v;
        if(v == fa) continue;
        dfs(v,u);
        if(!tcol[v]) continue;
        tcol[u] += tcol[v];
        if(color[u])
        {
            dp[u] = dp[u]*(dp[v]+del[v])%mod;
        }
        else
        {
            dp[u] = dp[u]*(dp[v]+del[v])%mod + del[u]*dp[v]%mod;
            dp[u] %= mod;
            del[u] = del[u]*(dp[v]+del[v])%mod;
        }
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int n;
    scanf("%d",&n);
    memset(head,0xff,sizeof(head));
    nEdge = -1;
    int u;
    for(int i = 2;i <= n;++i)
    {
        scanf("%d",&u);
        u++;
        AddEdges(u,i);
    }
    for(int i = 1;i <= n;++i)
        scanf("%d",&color[i]);
    dfs(1,-1);
    printf("%I64d
",dp[1]);
    return 0;
}

CF 461B - 트리 DP(Appleman and Tree)

좋은 웹페이지 즐겨찾기