2015
09-18

# Cirno’s Present

One day, three fairies, Sunny, Luna and Star visited Cirno’s house. Cirno was very happy, so she decided to give a present to them.
Cirno’s present was a tree with N nodes. Each node of the tree has an equal possibility to be owned by one of Sunny, Luna or Star. After having decided every node’s owner, Cirno cut the edges that connect different owner’s nodes, after which each of the three fairies got some connected component of nodes (possibly none).
Then each of the three fairies had to spend some magical energy repairing the components she got. Suppose she had X components containing odd number of nodes and Y components containing even number of nodes, the magical energy she would spend equals max(0, X – Y ).
Cirno would compensate for the energy they spent with some food, so she asked you the expectation of the total energy the three fairies would spend, and your task is to find out the answer.
To make it simpler, as it’s easy to prove the multiplication of the expectation and the Nth power of three makes an integer, your task is to find the remainder of the multiplication divided by 109 + 7.

There are several test cases, please process till EOF.
Each test case starts with a line containing one integer N (1 <= N <= 300). Then follows N – 1 lines, each contains two integers u and v (1 <= u, v <= N), representing an edge between node u and node v.

There are several test cases, please process till EOF.
Each test case starts with a line containing one integer N (1 <= N <= 300). Then follows N – 1 lines, each contains two integers u and v (1 <= u, v <= N), representing an edge between node u and node v.

1
2
1 2
3
2 1
1 3

3
12
51

非常值得一做的树形dp.

dp状态:dp[i][j][k],i代表对应的点,j有3个取值,0代表不取当前的点,1代表取当前的点并且当前点所在联通块的个数为奇数个,2代表为偶数个,k代表x-y的值.(注意dp表示的个数并不包括当前根节点的状态,因为当前根节点的状态还要需要其父亲)

dp[u][0][x+y]=dp[u][0][x]*dp[v][0][y]+dp[u][0][x]*dp[v][1][y-1]+dp[u][0][x]*dp[v][2][y+1]
dp[u][1][x+y]=dp[u][1][x]*dp[v][0][y]+dp[u][1][x]*dp[v][2][y]+dp[u][2][x]*dp[v][1][y]
dp[u][2][x+y]=dp[u][2][x]*dp[v][0][y]+dp[u][1][x]*dp[v][1][y]+dp[u][2][x]*dp[v][2][y]

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int MOD = 1000000007;
const int base = 160;
vector<int> g[305];
int dp[305][3][505];
int  t[3][505];
int low[305], high[305];
int n;

{
x += y;
while (x < MOD) {
x += MOD;
}
while (x >= MOD) {
x -= MOD;
}
}

int make_mul(int a, int b, int c, int d, int e, int f)
{
int v = 0;
add(v, 1ll * a * b % MOD);
add(v, 1ll * c * d % MOD);
add(v, 1ll * e * f % MOD);
return v;
}

void dfs(int u, int fu)
{
dp[u][0][base] = 2;
dp[u][1][base] = 1;
low[u] = 0, high [u] = 0;
int size = (int)g[u].size();
for (int i = 0; i < size; ++ i) {
int v = g[u][i];
if (v == fu)    continue;
dfs(v, u);
memset(t, 0, sizeof(t));
for (int x = low[u]; x <= high[u]; ++ x) {
for (int y = low[v] - 1; y <= high[v] + 1; ++ y) {
if (x + y > n || x + y < -n)  continue;
add(t[0][x + y + base], make_mul(dp[u][0][x + base], dp[v][0][y + base], dp[u][0][x + base], dp[v][1][y - 1 + base], dp[u][0][x + base], dp[v][2][y + 1 + base]));
add(t[1][x + y + base], make_mul(dp[u][1][x + base], dp[v][0][y + base], dp[u][1][x + base], dp[v][2][y + base], dp[u][2][x + base], dp[v][1][y + base]));
add(t[2][x + y + base], make_mul(dp[u][2][x + base], dp[v][0][y + base], dp[u][1][x + base], dp[v][1][y + base], dp[u][2][x + base], dp[v][2][y + base]));
if (t[0][x + y + base] != 0) {
if (x + y < low[u]) low[u] = x + y;
if (x + y > high[u])    high[u] = x + y;
}
if (t[1][x + y + base] != 0) {
if (x + y < low[u]) low[u] = x + y;
if (x + y > high[u])    high[u] = x + y;
}
if (t[2][x + y + base] != 0) {
if (x + y < low[u]) low[u] = x + y;
if (x + y > high[u])    high[u] = x + y;
}
}
}
for (int j = low[u]; j <= high[u]; ++ j) {
dp[u][0][j + base] = t[0][j + base];
dp[u][1][j + base] = t[1][j + base];
dp[u][2][j + base] = t[2][j + base];
}
}
}

int main()
{
while (scanf("%d", &n) == 1) {
for (int i = 1; i <= n; ++ i) {
g[i].clear();
}
memset(dp, 0, sizeof(dp));
int a, b;
for (int i = 1; i < n; ++ i) {
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1, 0);
int ans = 0;
for (int i = -1; i <= high[1]; ++ i) {
add(ans, 1ll * max(i, 0) * dp[1][0][i + base] % MOD);
add(ans, 1ll * max(i + 1, 0) * dp[1][1][i + base] % MOD);
add(ans, 1ll * max(i - 1, 0) * dp[1][2][i + base] % MOD);
}
ans = (int)(3ll * ans % MOD);
printf("%d\n", ans);
}
return 0;
}