2015
04-15

# Distinct Subtrees

Given an unrooted tree with n nodes, the subtree is defined as a connected component of the given tree. Two subtrees are considered the same if there exists a map from nodes of one tree to another so that the edges of both trees are corresponding the same pair of nodes after mapping.
Your task is to find out how many distinct subtrees for a given unrooted tree.

The input consists of multiple test cases. The first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains one integer n denoting the number of nodes of the given tree. (1 <= n <= 15)
Then n-1 lines follow, each line contains two integers denoting an edge of the tree (x, y).

The input consists of multiple test cases. The first line of input contains an integer denoting the number of test cases.
For each test case, the first line contains one integer n denoting the number of nodes of the given tree. (1 <= n <= 15)
Then n-1 lines follow, each line contains two integers denoting an edge of the tree (x, y).

2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8

Case #1: 3
Case #2: 21

/*******************************************************************************
去年上海赛区热身赛的一道题，树的最小表示模板题。解法就是用二进制枚举所有可能的联通子图，然后

*******************************************************************************/
#include <iostream>
#include <functional>
#include <algorithm>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <utility>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <limits>
#include <memory>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )
#define CLR(x, k) memset((x), (k), sizeof(x))
#define CPY(t, s) memcpy((t), (s), sizeof(s))
#define SC(t, s) static_cast<t>(s)
#define LEN(s) static_cast<int>( strlen((s)) )
#define SZ(s) static_cast<int>( (s).size() )

typedef double LF;
typedef __int64 LL;		//VC
typedef unsigned __int64 ULL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;

typedef vector<int> VI;
typedef vector<char> VC;
typedef vector<double> VF;
typedef vector<string> VS;

template <typename T>
T sqa(const T & x) {return x * x;}
template <typename T>
T ll(const T & x) {return x << 1;}
template <typename T>
T rr(const T & x) {return x << 1 | 1;}
template <typename T>
T gcd(T a, T b)
{
if (!a || !b)
{
return max(a, b);
}
T t;
while (t = a % b)
{
a = b;
b = t;
}
return b;
};

const int INF_INT = 0x3f3f3f3f;
const LL INF_LL = 0x7fffffffffffffffLL;		//15f
const double oo = 10e9;
const double eps = 10e-7;
const double PI = acos(-1.0);

#define  ONLINE_JUDGE

const int MAXV = 10004;
const int MAXN = 200004;

int test, n;
struct Node
{
Node * next[2];
bool end_sign;
}trie[MAXN], * const root = trie;
int ncnt;
VI G[MAXV];
bool hs[MAXV];

void initTrie()
{
ncnt = 1;
for (int i = 0; i < 2; ++i)
{
root->next[i] = NULL;
}
root->end_sign = false;
return ;
}
Node * createNode()
{
for (int i = 0; i < 2; ++i)
{
trie[ncnt].next[i] = NULL;
}
trie[ncnt].end_sign = false;
return &trie[ncnt++];
}
bool insertTrie(const string & str)
{
Node * ptr = root;
int len = SC(int, str.length());
for (int i = 0; i < len; ++i)
{
int t = str[i] - '0';
if (NULL == ptr->next[t])
{
ptr->next[t] = createNode();
}
ptr = ptr->next[t];
}
if (ptr->end_sign)
{
return false;
}
ptr->end_sign = true;
return true;
}
void addEdge(int u, int v)
{
G[u].push_back(v);
return ;
}
void search(int u, int state)
{
hs[u] = true;
for (VI::iterator it = G[u].begin(); it != G[u].end(); ++it)
{
int v = *it;
if ((1 << v) & state)
{
if (!hs[v])
{
search(v, state);
}
}
}
return ;
}
bool connectedJudge(int state)
{
CLR(hs, false);
for (int i = 0; i < n; ++i)
{
if ((1 << i) & state)
{
search(i, state);
break ;
}
}
for (int i = 0; i < n; ++i)
{
if ((1 << i) & state)
{
if (!hs[i])
{
return false;
}
}
}
return true;
}
string dfs(int u, string str, int state)
{
VS vs;
hs[u] = true;
for (VI::iterator it = G[u].begin(); it != G[u].end(); ++it)
{
int v = *it;
if ((1 << v) & state)
{
if (!hs[v])
{
vs.push_back(dfs(v, "0", state) + "1");
}
}
}
sort(vs.begin(), vs.end());
for (VS::iterator it = vs.begin(); it != vs.end(); ++it)
{
str += *it;
}
return str;
}
bool insertJudge(int state)
{
bool sign = false;
for (int u = 0; u < n; ++u)
{
if ((1 << u) & state)
{
CLR(hs, false);
if (insertTrie(dfs(u, "", state)))
{
sign = true;
}
}
}
return sign;
}
void ace()
{
int cas = 1;
int u, v;
int res;
for (scanf("%d", &test); test--; ++cas)
{
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
G[i].clear();
}
initTrie();
for (int i = 0; i < n - 1; ++i)
{
scanf("%d %d", &u, &v);
--u;
--v;
addEdge(u, v);
addEdge(v, u);
}
res = 0;
for (int state = 1; state < (1 << n); ++state)
{
if (!connectedJudge(state))
{
continue ;
}
if (insertJudge(state))
{
++res;
}
}
printf("Case #%d: %d\n", cas, res);
}
return ;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ace();
return 0;
}
/*******************************************************************************
Test Data...
2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8
*******************************************************************************/


, ,
1. 第二个方法挺不错。NewHead代表新的头节点，通过递归找到最后一个节点之后，就把这个节点赋给NewHead，然后一直返回返回，中途这个值是没有变化的，一边返回一边把相应的指针方向颠倒，最后结束时返回新的头节点到主函数。

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。

3. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

4. I like your publish. It is great to see you verbalize from the coronary heart and clarity on this essential subject matter can be easily noticed.