Codeforces 461B - Appleman and Tree 樹狀DP
來源：程序員人生 發(fā)布時間：2014-10-12 15:42:36 閱讀次數(shù)：3133次
一棵樹上有K個黑色節(jié)點，剩余節(jié)點都為白色，將其劃分成K個子樹，使得每棵樹上都只有1個黑色節(jié)點，共有多少種劃分方案。
個人感覺這題比較難。假設(shè)dp(i,0..1)代表的是以i為根節(jié)點的子樹種有0..1個黑色節(jié)點的劃分方案數(shù)。
當節(jié)點i為白色時，對于它的每個孩子的節(jié)點處理：
求dp(i, 0)時有：
1，將該節(jié)點與孩子節(jié)點相連，但要保證孩子節(jié)點所在的子樹種沒有黑色節(jié)點；
2，將該節(jié)點不與該孩子節(jié)點相連，則該孩子節(jié)點要保證所在子樹種有黑色節(jié)點；
即dp(i, 0) = π(dp(j,0 ) + dp(j, 1)) ，其中j為i的孩子節(jié)點
求dp(i,1)時有：
將該節(jié)點與其中每個孩子節(jié)點中的一個相連，并且保證該孩子節(jié)點所在子樹中有1個黑色節(jié)點（所以共有K種情況，K為該節(jié)點的孩子數(shù)），并且對于剩下的節(jié)點可以選擇連也可以選擇不連，如果連接，則保證該子節(jié)點所在子樹中沒有黑色，如果不連，則要保證有黑色，所以對于剩下的每個
子節(jié)點的處理方案書有dp(j,0) + dp(j,1)個，然后將每個孩子處理的方案書相乘即可，最后將所有的方案相加即可。
當節(jié)點i為黑色的時候，求dp(i, 0) 肯定是0；
求dp(i, 1)時對于i的每個子節(jié)點也是有兩種選擇，連或者不連，如果連接，則保證該子節(jié)點所在子樹中沒有黑色，如果不連，則要保證有黑色，即對于每個子節(jié)點的處理數(shù)共有
dp(j, 0) + dp(j, 1)個，然后將每個孩子處理的方案數(shù)相乘。
最終dp(0,1)即為答案，這里假設(shè)0節(jié)點為根節(jié)點。
過程中可以加個小小的優(yōu)化，當一個子節(jié)點所在的整棵子樹中若沒有黑色節(jié)點，那么該節(jié)點肯定與其父節(jié)點相連，所以計算時可以不考慮該節(jié)點。
#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)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
