Language: C++


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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define int ll
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
const int inf = 1000000001;
const ll INF = 2e18;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };



class CentroidDecomposition {
public:
	int n; //頂点数
	vii G; //グラフの隣接リスト表現
	vector<bool> isused; //その頂点がすでに分割に使われているか
	vi subtreesize; //部分木のサイズ,更新される
	vi parent;
	vi centroid; //重心が後ろに追加されていく
	vector<char> ans;

	CentroidDecomposition(int n) : n(n) {
		G.resize(n); isused.resize(n);
		subtreesize.resize(n); parent.resize(n);
		ans.resize(n);
	}

	void add_edge(int u, int v) {
		G[u].push_back(v); G[v].push_back(u);
	}

	int search_centroid(int now, int par, int size) {
		subtreesize[now] = 1;
		parent[now] = par;
		bool iscentroid = true;
		for (int i = 0; i < G[now].size(); i++) {
			int child = G[now][i];
			if (child == par) continue;
			if (isused[child]) continue;
			int child_size = search_centroid(child, now, size);
			if (child_size > size / 2) iscentroid = false;
			subtreesize[now] += child_size;
		}
		if (size - subtreesize[now] > size / 2) {
			iscentroid = false;
		}
		if (iscentroid) {
			centroid.push_back(now);
		}
		return subtreesize[now];
	}

	//問題によって変わる
	void solve(int root, char c, int size) {
		search_centroid(root, -1, size);
		int cent = centroid.back();
		isused[cent] = true;
		ans[cent] = c;
		rep(i, G[cent].size()) {
			int ch = G[cent][i];
			if (isused[ch]) {
				continue;
			}
			if (parent[ch] == cent) {
				solve(ch, c + 1, subtreesize[ch]);
			}
			else {
				solve(ch, c + 1, size - subtreesize[cent]);
			}
		}
		return;
	}

	int dfs(int now, int parent) {
		int cnt = 1;
		rep(i, G[now].size()) {
			int ch = G[now][i];
			if (ch == parent) {
				continue;
			}
			cnt += dfs(ch, now);
		}
		return cnt;
	}


};


ll dp[5151][5151];
vector<int>pat[5151];
bool flag[5151];
int num;
int cent;
int dfs(int node)
{
	if (flag[node])return 0;
	flag[node] = true;
	int s = 1, maxi = 0;
	for (int i = 0; i < pat[node].size(); i++)
	{
		int r = dfs(pat[node][i]);
		maxi = max(maxi, r);
		s += r;
	}
	if ((num - s) * 2 <= num&&maxi * 2 <= num)
	{
		if (cent == -1)cent = node;
		else
		{
			ll ans = 1;
			for (int i = 1; i <= num / 2; i++)ans = ans*i%mod*i%mod;
			printf("%lld\n", ans);
			exit(0);
		}
	}
	return s;
}
#define SIZE 100000
ll inv[SIZE + 1];
ll kai[SIZE + 1];
ll invkai[SIZE + 1];
void invinit()
{
	inv[1] = 1;
	for (int i = 2; i <= SIZE; i++)
	{
		inv[i] = mod - (mod / i)*inv[mod%i] % mod;
	}
	kai[0] = invkai[0] = 1;
	for (int i = 1; i <= SIZE; i++)
	{
		kai[i] = kai[i - 1] * i%mod;
		invkai[i] = invkai[i - 1] * inv[i] % mod;
	}
}
ll com(ll a, ll b)
{
	if (b < 0 || a < b)return 0;
	return (invkai[b] * invkai[a - b]) % mod*kai[a] % mod;
}
int main()
{
	scanf("%d", &num);
	invinit();
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	cent = -1;
	dfs(0);
	vector<int>v;
	fill(flag, flag + num, false);
	flag[cent] = true;
	for (int i = 0; i < pat[cent].size(); i++)v.push_back(dfs(pat[cent][i]));
	dp[0][0] = 1;
	for (int i = 0; i < v.size(); i++)
	{
		for (int j = 0; j <= num; j++)
		{
			if (dp[i][j] == 0)continue;
			ll now = 1;
			for (int k = 0; k <= v[i]; k++)
			{
				dp[i + 1][j + k] = (dp[i + 1][j + k] + dp[i][j] * now%mod*com(v[i], k)) % mod;
				now *= v[i] - k;
				now %= mod;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i <= num; i++)
	{
		ll t = dp[v.size()][i] * kai[num - i] % mod;
		//printf("%lld\n", dp[v.size()][i]);
		if (i % 2 == 0)ans += t;
		else ans += mod - t;
	}
	printf("%lld\n", ans%mod);
}

Compiler output:
a.cc:9:13: error: '::main' must return 'int'
    9 | #define int ll
      |             ^~
a.cc:165:1: note: in expansion of macro 'int'
  165 | int main()
      | ^~~