Submission #1854812

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 2005;
const int mod = 1e9 + 7;
const int half = 5e8 + 4;

int n;
int sz[N]; // number of edges
int prd[N];
int f[N][N][3]; // (i, j, k) subtree i, number of edges: j, number of edges connect to i: k
int g[N][N][3]; // knapsack
vector<int> G[N];

// a fixed set of edges has number of edges: i and number of components: j
// number of ways *= (2 ^ j) * (n - i)! * ((-1) ^ i)

void add(int &x, int y) {
	x = (x + y) >= mod ? (x + y - mod) : (x + y);
}

void dfs(int u) {
	for (auto v : G[u]) dfs(v);
	int id = 0;
	g[0][0][0] = 1;
	for (auto v : G[u]) {
		++id;
		// reset
		for (int i = 0; i <= sz[u] + sz[v] + 1; ++i) {
			for (int j = 0; j <= 2; ++j) g[id][i][j] = 0;
		}
		for (int i = 0; i <= sz[u]; ++i) {
			for (int j = 0; j <= sz[v]; ++j) {
				for (int k = 0; k <= 2; ++k) {
					// do not use u-v edge
					for (int l = 0; l <= 2; ++l) {
						add(g[id][i + j][k], 1LL * g[id - 1][i][k] * f[v][j][l] % mod); 
					}
					// use u-v edge
					if (k == 0) {
						add(g[id][i + j + 1][k + 1], 2LL * g[id - 1][i][k] * f[v][j][0] % mod);
						add(g[id][i + j + 1][k + 1], 1LL * g[id - 1][i][k] * f[v][j][1] % mod);
					}
					if (k == 1) {
						add(g[id][i + j + 1][k + 1], 1LL * g[id - 1][i][k] * f[v][j][0] % mod);
						add(g[id][i + j + 1][k + 1], 1LL * g[id - 1][i][k] * f[v][j][1] % mod * half % mod);
					}
				}
			}
		}
		sz[u] += sz[v] + 1;
	}
	// cout << "At " << u << '\n';
	for (int i = 0; i <= sz[u]; ++i) {
		for (int j = 0; j <= 2; ++j) {
			f[u][i][j] = g[id][i][j];
			// cout << f[u][i][j] << ' ' << i << ' ' << j << '\n';
 		}
 	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 2; i <= n; ++i) {
		int p; cin >> p, G[p].push_back(i);
	}
	dfs(1);
	prd[0] = 1; 
	for (int i = 1; i <= n; ++i) prd[i] = 1LL * prd[i - 1] * i % mod;
	int res = 0;
	for (int i = 0; i < n; ++i) {
		int tmp = 0;
		for (int j = 0; j <= 2; ++j) add(tmp, f[1][i][j]);
		// inclusion-exclusion
		if (i & 1) tmp = mod - tmp;
		add(res, 1LL * tmp * prd[n - i] % mod);
	}
	cout << res;
}

Submission Info

Judge Result