Appleman and Tree - CF 461B

 প্রবলেমটা মূলত ডিপি অন ট্রি প্রবলেম। এখানে একটা ট্রি দেয়া আছে , যার প্রত্যেকটা নোড হয় ব্লাক অথবা হোয়াইট। এখন লক্ষ্য করি, ট্রির যেকোনো একটি এজ যদি আমরা ডিলিট করি তাহলে দুইটি নতুন ট্রি পাবো । দুটি এজ ডিলিট করলে আমরা তিনটি নতুন ট্রি পাবো। অর্থাৎ , ক সংখ্যক এজ ডিলিট করলে আমরা ক+১ টি নতুন ট্রি/ কম্পোনেন্ট পাবো। কিন্তু আমাদের এমন ভাবে এজগুলো ডিলিট করতে হবে যাতে  ডিলিট করার পর প্রত্যেকটা কম্পোনেন্ট এ একটি মাত্র ব্লাক নোড থাকে। বলতে হবে এমন কত উপায়ে ট্রি এর এজগুলোকে ডিলিট করা যাবে।

কিছু বিষয় লক্ষ্য করা যাক। যদি ট্রি তে সবগুলো নোড ই ব্লাক হয় তাহলে এক উপায়েই  তাদের এজগুলো ডিলিট করা যায় । যদি ট্রি এর রুট নোড ব্লাক হয় এবং চাইল্ড নোড হোয়াইট হয়,  তাহলে তার চাইল্ড নোডের সাথে থাকা এজটিকে আমরা ডিলিট করতেও পারি নাও করতে পারি। রুট নোড হোয়াইট আর চাইল্ড নোড ব্লাক হলেও একই বিষয়। হোয়াইট নোড এর চাইল্ড হোয়াইট নোড হলেও তাই । 
সুতরাং , আমাদের যদি জানা থাকে চাইল্ড নোড গুলোর প্রত্যেক্টার জন্য কত উপায়ে এজ স্প্লিট করা যায় আমরা রুট নোডের জন্যও কম্বিনেশন বের করে ফেলতে পারি। এখানে , খেয়াল রাখতে হবে দুটি কম্পনেট এ কিন্তু একটি ব্লাক নোড থাকতে হবে। সুতরাং, একাধিক ব্লাক নোডের ক্ষেত্রে এজ স্প্লিট করতে হবে। একাধিক হোয়াইট নোড থাকতে কিন্তু কোন সমস্যা নেই।

#include<bits/stdc++.h>
#define M   1000000007
#define lli long long int
#define pb push_back
#define pf printf
#define sc scanf
using namespace std;
const int sz=1e5+7;
vector<int>g[sz];
int col[sz];
lli dp[sz][2];

void dfs(int u)
{
    dp[u][1]=col[u];    //if black
    dp[u][0]=1-col[u];  //if white

    lli ways=0;
    for(auto v:g[u])
    {
        dfs(v);
        dp[u][1]=( (dp[u][1]*(dp[v][1]+dp[v][0]))%M + (dp[u][0]*dp[v][1])%M )%M;
        dp[u][0]=(dp[u][0]*(dp[v][1]+dp[v][0]))%M;
    }

}

void test(int T)
{
    int n,i,p;
    sc("%d",&n);
    for(i=1; i<n; i++)
        sc("%d",&p),g[p].pb(i);
    for(i=0; i<n; i++)
        sc("%d",&col[i]);
    dfs(0);

    pf("%lld\n",dp[0][1]);
}
void Test()
{
    int T;
    scanf("%d",&T);
    for(int cs=1; cs<=T; cs++)
        test(cs);
}
int main()
{
    //Test();
    test(1);
    return 0;
}