UVA 11174 Stand in a Line 樹形dp+計數

UVA 11174 Stand in a Line 樹形dp+計數

題目鏈接：點擊打開鏈接

題意：白書的P103.

加個虛根就可以了。。。然後就是一個多重集排列。

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int N = 40100;
	ArrayList[] G = new ArrayList[N];
	static long mod = 1000000007;
	long[] way = new long[N];
	long[] fac = new long[N];
	int n, m;
	int[] father = new int[N], siz = new int[N];
	long Pow(long x, long y){
		long ans = 1;
		while(y > 0){
			if(y%2 == 1L)
				ans = (ans*x)%mod;
			x = (x*x)%mod;
			y >>= 1;
		}
		return ans;
	}
	void dfs(int u, int fa){
		siz[u] = 1; way[u] = 1L;
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u].get(i); if(v == fa)continue;
			dfs(v, u);
			siz[u] += siz[v];
			way[u] = (way[u]*way[v])%mod;
		}
		way[u] = (way[u]* fac[siz[u]-1]) %mod;
		for(int i = 0; i < G[u].size(); i++){
			int v = G[u].get(i); if(v == fa)continue;
			way[u] = (way[u] * Pow(fac[siz[v]], mod-2))%mod;
		}
	}
	void init(){
		n = cin.nextInt();	m = cin.nextInt();
		for(int i = 0; i <= n; i++){
			father[i] = 0;
			G[i].clear();
		}
		while(m-- > 0){
			int u = cin.nextInt(), v = cin.nextInt();
			G[v].add(u);
			father[u] = v;
		}
		for(int i = 1; i <= n; i++)
			if(father[i] == 0){
				G[0].add(i);
			}
	}
	void work() {		
		for(int i = 0; i < N; i++)G[i] = new ArrayList();
		fac[0] = 1L;
		for(int i = 1; i < N; i++)	fac[i] = fac[i-1]*i%mod;
		int T = cin.nextInt();
		while(T-->0){
			init();
			dfs(0,0);
			out.println(way[0]);
		}
	}

	Main() {
		cin = new Scanner(System.in);
		out = new PrintWriter(System.out);
	}

	public static void main(String[] args) {
		Main e = new Main();
		e.work();
		out.close();
	}

	public Scanner cin;
	public static PrintWriter out;
}