Such a tour exists only when the tree is a caterpiller tree which is a tree consisting of a straight path with some leafs attached to nodes on that path. Using this observation, getting a recurrence and solving it using Dynamic Programming is greatly simplified. Also, working out some examples on paper, it is easy to see that the answer is 2 * n1! * ... * nk! where n1,..,nk are the number of leafs attached to each node on the path defining the caterpiller tree. A special case is when the tree is a star, when the answer is simply (n - 1)!. See: http://en.wikipedia.org/wiki/Caterpillar_tree
-
-
Save aishraj/1361927 to your computer and use it in GitHub Desktop.
Bytelandian Tours Solution (InterviewStreet CodeSprint Fall 2011)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<vector> | |
#include<stdio.h> | |
#include<set> | |
#include<string.h> | |
#include<stdlib.h> | |
using namespace std ; | |
#define INF (int)1e9 | |
#define MOD 1000000007 | |
#define MAXN 10002 | |
vector<int> G[MAXN] ; | |
int n,fac[MAXN] ; | |
char isLeaf[MAXN] ; | |
int solve() | |
{ | |
int ret = 1,path = n ; | |
for(int i = 0;i < n;i++) path -= isLeaf[i] = G[i].size() == 1 ; | |
for(int i = 0;i < n;i++) if(!isLeaf[i]) | |
{ | |
int ct = 0,ct2 = 0 ; | |
for(int j = 0;j < G[i].size();j++) | |
if(!isLeaf[G[i][j]]) ct++ ; | |
else ct2++ ; | |
if(ct > 2) return 0 ; | |
ret = 1LL * ret * fac[ct2] % MOD ; | |
} | |
return path == 1 ? ret : 2 * ret % MOD ; | |
} | |
int main() | |
{ | |
fac[0] = 1 ; | |
for(int i = 1;i < MAXN;i++) fac[i] = 1LL * i * fac[i - 1] % MOD ; | |
int runs ; | |
scanf("%d",&runs) ; | |
while(runs--) | |
{ | |
scanf("%d",&n) ; | |
for(int i = 0;i < MAXN;i++) G[i].clear() ; | |
for(int i = 1;i < n;i++) | |
{ | |
int a,b ; | |
scanf("%d%d",&a,&b) ; | |
G[a].push_back(b) ; | |
G[b].push_back(a) ; | |
} | |
int ret = solve() ; | |
printf("%d\n",ret) ; | |
} | |
return 0 ; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment