hdu5379(2015 멀티 스쿨7)--Mahjong tree(구조+dfs)

제목 링크: 클릭하여 링크 열기
제목의 대의: n개의 노드를 가진 나무를 제시한다. 1의 노드는 뿌리이다. 현재 1부터 n까지 n개의 수를 각 노드에 놓고 각 하위 나무의 숫자는 연속적이며 같은 부 노드의 노드 숫자는 연속적이다. 몇 가지가 있느냐고 묻는다.
만약에 하나의 노드 u에 대해 말하자면 하위 노드vi수가sum이면 하위 노드는num이고 sum-num>2라면 구조될 수 없으며,sum-num==2이면 방안은 dp[u]=∏dp[vi]*(num!),만약 2보다 작으면 방안은 dp[u] = ∏dp[vi]* (num!)*2 잔액을 주의하다

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define maxn 100010
#define LL __int64
const int Mod = 1e9+7 ;
struct node{
    int v , next ;
}edge[maxn<<1] ;
int head[maxn] , cnt ;
int leaf[maxn] , flag ;
LL s[maxn] , dp[maxn] ;
void add(int u,int v) {
    edge[cnt].v = v ; edge[cnt].next = head[u] ;
    head[u] = cnt++ ;
}
void dfs(int u,int fa) {
    int i , v , num = 0 , sum = 0 ;
    dp[u] = leaf[u] = 1 ;
    for(i = head[u] ; i != -1 ; i = edge[i].next) {
        v = edge[i].v ;
        if( v == fa ) continue ;
        leaf[u] = 0 ;
        dfs(v,u) ;
        dp[u] = dp[u]*dp[v]%Mod ;
        sum++ ;
        if( leaf[v] ) num++ ;
    }
    if( sum == 0 ) return ;
    if( sum-num > 2 ) flag = 1 ;
    if( sum-num == 2 )
        dp[u] = dp[u]*s[num]%Mod ;
    else
        dp[u] = dp[u]*s[num]*2%Mod ;
}
int main() {
    int t , step = 0 ;
    int n , i , j , u , v ;
    s[0] = 1 ;
    for(i = 1 ; i <= 100000 ; i++)
        s[i] = s[i-1]*i%Mod ;
    scanf("%d", &t) ;
    while( t-- ) {
        scanf("%d", &n) ;
        memset(head,-1,sizeof(head)) ;
        cnt = 0 ;
        for(i = 1;  i < n ; i++) {
            scanf("%d %d", &u, &v) ;
            add(u,v) ;
            add(v,u) ;
        }
        flag = 0 ;
        dfs(1,-1) ;
        if( flag ) dp[1] = 0 ;
        printf("Case #%d: %I64d
", ++step, dp[1]) ;
    }
    return 0 ;
}