Codeforces 461B - Appleman and Tree 樹狀DP
來源：程序員人生 發(fā)布時(shí)間：2014-10-12 15:42:36 閱讀次數(shù)：3138次
一棵樹上有K個(gè)黑色節(jié)點(diǎn)，剩余節(jié)點(diǎn)都為白色，將其劃分成K個(gè)子樹，使得每棵樹上都只有1個(gè)黑色節(jié)點(diǎn)，共有多少種劃分方案。
個(gè)人感覺這題比較難。假設(shè)dp(i,0..1)代表的是以i為根節(jié)點(diǎn)的子樹種有0..1個(gè)黑色節(jié)點(diǎn)的劃分方案數(shù)。
當(dāng)節(jié)點(diǎn)i為白色時(shí)，對(duì)于它的每個(gè)孩子的節(jié)點(diǎn)處理：
求dp(i, 0)時(shí)有：
1，將該節(jié)點(diǎn)與孩子節(jié)點(diǎn)相連，但要保證孩子節(jié)點(diǎn)所在的子樹種沒有黑色節(jié)點(diǎn)；
2，將該節(jié)點(diǎn)不與該孩子節(jié)點(diǎn)相連，則該孩子節(jié)點(diǎn)要保證所在子樹種有黑色節(jié)點(diǎn)；
即dp(i, 0) = π(dp(j,0 ) + dp(j, 1)) ，其中j為i的孩子節(jié)點(diǎn)
求dp(i,1)時(shí)有：
將該節(jié)點(diǎn)與其中每個(gè)孩子節(jié)點(diǎn)中的一個(gè)相連，并且保證該孩子節(jié)點(diǎn)所在子樹中有1個(gè)黑色節(jié)點(diǎn)（所以共有K種情況，K為該節(jié)點(diǎn)的孩子數(shù)），并且對(duì)于剩下的節(jié)點(diǎn)可以選擇連也可以選擇不連，如果連接，則保證該子節(jié)點(diǎn)所在子樹中沒有黑色，如果不連，則要保證有黑色，所以對(duì)于剩下的每個(gè)
子節(jié)點(diǎn)的處理方案書有dp(j,0) + dp(j,1)個(gè)，然后將每個(gè)孩子處理的方案書相乘即可，最后將所有的方案相加即可。
當(dāng)節(jié)點(diǎn)i為黑色的時(shí)候，求dp(i, 0) 肯定是0；
求dp(i, 1)時(shí)對(duì)于i的每個(gè)子節(jié)點(diǎn)也是有兩種選擇，連或者不連，如果連接，則保證該子節(jié)點(diǎn)所在子樹中沒有黑色，如果不連，則要保證有黑色，即對(duì)于每個(gè)子節(jié)點(diǎn)的處理數(shù)共有
dp(j, 0) + dp(j, 1)個(gè)，然后將每個(gè)孩子處理的方案數(shù)相乘。
最終dp(0,1)即為答案，這里假設(shè)0節(jié)點(diǎn)為根節(jié)點(diǎn)。
過程中可以加個(gè)小小的優(yōu)化，當(dāng)一個(gè)子節(jié)點(diǎn)所在的整棵子樹中若沒有黑色節(jié)點(diǎn)，那么該節(jié)點(diǎn)肯定與其父節(jié)點(diǎn)相連，所以計(jì)算時(shí)可以不考慮該節(jié)點(diǎn)。
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
//int values[500001];
//long long sums[500001];
#define MODVALUE 1000000007
#define MOD(x) if((x) > MODVALUE) x %= MODVALUE;
struct Edge
{
int to;
int i;
int totalcolor;
Edge()
{
totalcolor = 0;
}
};
int compp(const void* a1, const void* a2)
{
return *((int*)a2) - *((int*)a1);
}
vector<Edge> G[100001];
int Color[100001];
long long res[100001][2];
//int TMP[100001];
bool Visited[100001];
void AddEdge(int from, int to)
{
Edge edge;
edge.to = to;
edge.i = G[to].size();
G[from].push_back(edge);
edge.to = from;
edge.i = G[from].size() - 1;
G[to].push_back(edge);
}
int CountColor(int node)
{
Visited[node] = true;
int count = 0;
if (Color[node])
{
count = 1;
}
for (int i = 0; i < G[node].size();i++)
{
Edge& edge = G[node][i];
if (!Visited[edge.to])
{
edge.totalcolor = CountColor(edge.to);
count += edge.totalcolor;
}
}
return count;
}
void GetAns(int node)
{
Visited[node] = true;
long long ans = 1;
int countofcolor = 0;
vector<int> TMP;
for (int i = 0; i < G[node].size(); i++)
{
Edge& edge = G[node][i];
if (Visited[edge.to])
{
continue;
}
//TMP[countofcolor++] = i;
GetAns(edge.to);
if (edge.totalcolor)
{
TMP.push_back(i);
countofcolor++;
//TMP[countofcolor++] = i;
}
}
res[node][0] = 0;
res[node][1] = 0;
long long tmp1 = 1;
long long tmp0 = 1;
if (!Color[node])
{
tmp1 = 0;
}
for (int i = 0; i < countofcolor; i++)
{
if (Color[node])
{
Edge& edge = G[node][TMP[i]];
tmp1 *= (res[edge.to][1] + res[edge.to][0]);
MOD(tmp1);
tmp0 = 0;
}
else
{
Edge& edge1 = G[node][TMP[i]];
tmp0 *= (res[edge1.to][1] + res[edge1.to][0]);
MOD(tmp0);
long long tmp3 = 1;
for (int j = 0; j < countofcolor; j++)
{
Edge& edge = G[node][TMP[j]];
if (i == j)
{
tmp3 *= res[edge.to][1];
MOD(tmp3);
}
else
{
tmp3 *= (res[edge.to][1] + res[edge.to][0]);
MOD(tmp3);
}
}
tmp1 += tmp3;
}
if (i == countofcolor - 1)
{
res[node][0] += tmp0;
res[node][1] += tmp1;
MOD(res[node][0]);
MOD(res[node][1]);
}
}
if (countofcolor == 0)
{
res[node][0] = Color[node] ? 0 : 1;
res[node][1] = Color[node] ? 1 : 0;
}
}
int main()
{
#ifdef _DEBUG
freopen("e:in.txt", "r", stdin);
#endif // _DEBUG
int n;
scanf("%d", &n);
for (int i = 0; i < n - 1; i++)
{
int value;
scanf("%d", &value);
AddEdge(i + 1, value);
}
for (int i = 0; i < n; i++)
{
int value;
scanf("%d", &value);
Color[i] = value;
}
memset(Visited, 0, sizeof(Visited));
CountColor(0);
memset(Visited, 0, sizeof(Visited));
GetAns(0);
printf("%I64d
", res[0][1]);
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
