HDU 4863 Centroid of a Tree （树形DP）

HDU 4863

Centroid of a Tree

Centroid of a Tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 49 Accepted Submission(s): 15

Problem Description

Given a tree T with N vertices, your task is calculating the number of the connected sub-tree of T, which has the same centroid as T. In order to define the centroid, some integer value will be associated to every vertex. Let’s consider the vertex k. If we remove the vertex k from the tree (along with its adjacent edges), the remaining graph will have only N-1 vertices and may be composed of more than one connected components. Each of these components is (obviously) a tree. The value associated to vertex k is the largest number of vertices contained by some connected component in the remaining graph, after the removal of vertex k. All the vertices for which the associated value is minimum are considered centroids. A graph can have an arbitrary number of centroids. However,it can be proved that for trees, there are only two possibilities: 1. The tree has precisely one centroid. 2. The tree has precisely two centroids. In this case, the two centroids are adjacent. Note that in case 2, we just consider that T has two centroids, you should only count the sub-tree which has the two same centroids as T.

Input

The first line of the date is an integer T, which is the number of the text cases. Then T cases follow each case starts of a number N descript above. Then N-1 lines follow, each line contains two integers x and y, which means that there is a edge between x and y in tree T, you can assume that the index of T is from 1 to N. 1 <= T <= 50, 1 <= N <= 200,

Output

For each case, output the case number first, then output the number of the connected sub-tree which has the same centroid as T. Give your answer modulo 10007.

Sample Input

5 1 2 1 2 3 1 2 1 3 4 1 2 1 3 1 4 5 1 2 1 3 1 4 4 5

Sample Output

Case 1: 1 Case 2: 1 Case 3: 2 Case 4: 5 Case 5: 6

Author

FZU

Source

2014 Multi-University Training Contest 1

本题需要找出和原来的树有相同重心的子树。   首先树形DP来求出重心。   然后如果重心有一个。 以重心为根，树形DP一下，得出dp\[i\]\[j\]表示i的子树保留j个结点的种数。 然后可以先求反面。 就是根的一颗子树大小大于剩下的和。 暴力枚举最大子树，DP出其余子树取i个的方法数f\[i\]. 然后枚举最大子树取几个。 使用总数减掉这个就是答案。 如果两个重心，可以分成两颗树，这两颗树大小要一样。   好题啊。。。  

/* ***************

Author        :kuangbin

Created Time  :2014/7/23 12:13:36

File Name     :E:\2014ACM\比赛\2014多校训练\2014多校1\HDU4863.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

const int MAXN = 220;

struct Edge

{

	int to,next;

}edge[MAXN*2];

int head[MAXN],tot;

void init()

{

	tot = 0;

	memset(head,-1,sizeof(head));

}

void addedge(int u,int v)

{

	edge[tot].to = v;

	edge[tot].next = head[u];

	head[u] = tot++;

}

int size[MAXN];

int mx[MAXN];

void dfs1(int u,int pre,int n)

{

	size[u] = 1;

	mx[u] = 0;

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(v == pre)continue;

		dfs1(v,u,n);

		size[u] += size[v];

		mx[u] = max(mx[u],size[v]);

	}

	mx[u] = max(mx[u],n-size[u]);

}

const int MOD = 10007;

int dp[MAXN][MAXN];//dp[i][j]是i子树取j个结点的方法数

void dfs_1(int u,int pre)

{

	size[u] = 1;

	dp[u][1] = 1;

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(v == pre)continue;

		dfs_1(v,u);

		size[u] += size[v];

		for(int j = size[u];j > 0;j--)

			for(int k = 1;k < j && k <= size[v];k++)

			{

				dp[u][j] += dp[u][j-k]*dp[v][k]%MOD;

				if(dp[u][j] >= MOD)dp[u][j] -= MOD;

			}

	}

}

int f[MAXN];

int solve1(int cen,int n)

{

	memset(dp,0,sizeof(dp));

	for(int i = 1;i <= n;i++)dp[i][0] = 1;

	dfs_1(cen,cen);

	int ans = 0;

	for(int i = head[cen];i != -1;i = edge[i].next)

	{

		int u = edge[i].to;

		memset(f,0,sizeof(f));

		f[0] = 1;

		for(int j = head[cen];j != -1;j = edge[j].next)

			if(j != i)

			{

				int v = edge[j].to;

				for(int y = n;y > 0;y--)

					for(int x = 1;x <= size[v] && x <= y;x++)

					{

						f[y] += f[y-x]*dp[v][x]%MOD;

						if(f[y] >= MOD)f[y] -= MOD;

					}

			}

		int tmp = f[0]%MOD;

		for(int j = 1;j <= size[u];j++)

		{

			ans += tmp*dp[u][j]%MOD;

			ans %= MOD;

			tmp += f[j];

			tmp %= MOD;

		}

	}

	int tot = 1;

	for(int i = head[cen];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		int tmp = 0;

		for(int j = 0;j <= size[v];j++)

		{

			tmp = (tmp+dp[v][j])%MOD;

		}

		tot = tot*tmp%MOD;

	}

	ans = tot-ans;

	ans = (ans%MOD+MOD)%MOD;

	return ans;

}

void dfs_2(int u,int pre,int no)

{

	size[u] = 1;

	dp[u][1] = 1;

	for(int i = head[u];i != -1;i = edge[i].next)

	{

		int v = edge[i].to;

		if(v == pre || v == no)continue;

		dfs_2(v,u,no);

		size[u] += size[v];

		for(int j = size[u];j > 0;j--)

			for(int k = 1;k < j && k <= size[v];k++)

			{

				dp[u][j] += dp[u][j-k]*dp[v][k]%MOD;

				if(dp[u][j] >= MOD)dp[u][j] -= MOD;

			}

	}

}

int solve2(int cen1,int cen2,int n)

{

	memset(dp,0,sizeof(dp));

	for(int i = 1;i <= n;i++)dp[i][0] = 1;

	dfs_2(cen1,cen1,cen2);

	dfs_2(cen2,cen2,cen1);

	int ans = 0;

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

	{

		ans += dp[cen1][i]*dp[cen2][i]%MOD;

		ans %= MOD;

	}

	return ans;

}

int main()

{

    //freopen("1003.in","r",stdin);

    //freopen("out.txt","w",stdout);

    int T;

	int iCase = 0;

	int n;

	scanf("%d",&T);

	while(T--)

	{

		iCase++;

		scanf("%d",&n);

		init();

		int u,v;

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

		{

			scanf("%d%d",&u,&v);

			addedge(u,v);

			addedge(v,u);

		}

		dfs1(1,1,n);

		int cen1,cen2;

		int cnt = 0;

		int MM = n;

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

		{

			if(mx[i] < MM)

			{

				MM = mx[i];

				cen1 = i;

				cnt = 1;

			}

			else if(mx[i] == MM)

			{

				cen2 = i;

				cnt = 2;

			}

		}

		if(cnt == 1)printf("Case %d: %d\n",iCase,solve1(cen1,n));

		else printf("Case %d: %d\n",iCase,solve2(cen1,cen2,n));

	}

    return 0;

}