Bytelandian Tours Solution (InterviewStreet CodeSprint Fall 2011)

Hint.md

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

problemsetter.cpp

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