http://codeforces.com/contest/461

A.水题



B.太挫了，竟然被hack了一发。。。。



C.贪心。。竟然没看出来时哈夫曼编码问题



D.题目大意：给一棵树，每一个点为白色或黑色，切断一些边，使得每一个连通块有且仅有一个黑点，问划分方案数。



树形DP,

设状态：

dp[v][0]表示以v为根的子树中没有黑点，dp[v][1]有一个黑点。

状态方程：

dp[v][1] = dp[v][1]*dp[son][0] + dp[v][0]*dp[son][1] + dp[v][1]*dp[son][1]

dp[v][0] = dp[v][0]*dp[son][0] + dp[v][0]*dp[son][1]

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod=1000000007;

const int maxn = 100000 + 100;

vector<int> g[maxn];

int clr[maxn];

LL dp[maxn][2];

int n;

void dfs(int u, int p)

{

    dp[u][clr[u]] = 1;

    for(int i=0; i<g[u].size(); ++i)

    {

        int &v = g[u][i];

        if(v==p) continue;

        dfs(v, u);

        dp[u][1] = (dp[u][1]*dp[v][0]%mod + dp[u][0]*dp[v][1]%mod + dp[u][1]*dp[v][1]%mod) % mod;

        dp[u][0] = (dp[u][0]*dp[v][1]%mod + dp[u][0]*dp[v][0]%mod) % mod;

    }

}

int main()

{

    scanf("%d", &n);

    int x;

    for(int i=1; i<n; ++i)

    {

        scanf("%d",&x);

        g[i].push_back(x);

        g[x].push_back(i);

    }

    for(int i=0; i<n; ++i)

    {

        scanf("%d", &clr[i]);

    }

    dfs(0, -1);

    printf("%I64d\n", dp[0][1]);

    return 0;

}

E.





Div1 D Appleman and Complicated Task





Div1 E Appleman and a Game