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;
}

1. 还好我们这边比较人性化，就地铁要检测。公交车不用喝。汽车门口的安检 最近一次我去，人家说 你就打开喝喝装装样子 不用真喝

2. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

3. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

4. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

5. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

6. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

7. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

8. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

9. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

10. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

11. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

12. 好久没来逛D站了感觉变化好大好大，第一次知道还是2014年，为了看喰种，那时候D站远没有现在这么花哨【划掉】。。。。。。我把D站推荐给我一同学，他现在说D站已经成为他的蹲据点了【笑】祝D站越办越好！！！！另外站长是我的！！！！

13. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

14. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

15. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

16. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

17. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

18. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

19. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

20. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……

21. 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛的爱琴海逍遥游 ……出境旅游 -> 【北京出发】＜意大利希腊13日阳光之旅＞圣托尼里岛 … 卡布里岛是意大利享誉国际的观光胜地，这里有极迷人的阳光与海滩、有优美的 ……