https://gmoj.net/senior/#main/show/6541

\(n<=5000\)

题解：

我感觉我和这种dp无缘，肝了两个小时拿了0分，还不如去写第三题。

​

首先这种排列，树上的，不难想到树上的笛卡尔树dp。

设\(f[i][j]\)表示\(i\)子树里\(j\)段balabala的。

​

再看这题，边的限制相当于\(x->fa[x]\)的边权=\(x子树内的段数\)，注意这题是一个环。

​

设\(f[i][j]\)表示\(i\)子树内，有\(j\)段，

我们发现如果段与段之间的顺序没有定，是不好做的，所以定段与段的顺序为一个圆排列。

又为了更加确定，我们设\(i\)在的那段是圆排列的开头。

​

考虑转移，有x和其一儿子y，要合并(x+已经转移过的儿子)的段和y的段。

注意因为边的限制，y的段是确定的，但x的段数不是确定的。

所以枚举x的段数i，设y有j段，再枚举合并成k段，这样有\(i+j-k\)个相邻的段合并了（注意这合并的两个段必须一个属于x一个属于y）。

因为是把y插到x的空位中（不能插到x的第一段的前面），再选一些地方合并，所以再枚举有x个空位中有u个空位插了y。

那么\(new\_f[x][k]+=f[x][i]*f[y][j]*C_{i}^u*C_{j-1}^{u-1}*C_{2u}^{i+j-k}*j\)

最后的\(*j\)是因为把y循环一下插进去也是要记录答案的。

答案就是\(f[1][0]*n\)。

​

考虑，现在最大的问题就是不能合并来自相同子树的段，不然就不用枚举u，组合数干过去就好了。

所以容斥这个限制，我们要的是恰好有0个来自相同的子树段合并了，现在容斥为至少\(v\)个，容斥系数就\((-1)^v\)

若原来大小是\(i\)，则要划分成\(i-v\)段，系数就是\(C_{i-1}^v\)。

​

然后再做刚才的dp，就不用枚举u了。

然而你发现复杂度没有变，因为每次要\(siz[x]^2\)的时间去把容斥的系数下传之类的，但是能过随机数据。

​

这个时候，我们就不用一个一个子节点合并了，直接合并所有的子节点。

因为每个子节点的段数是确定的，所以容斥系数下传复杂度就变成\(siz[x]\)了。

​

拆一下，设\(p[y]\)为y子节点原来的段数，\(q[y]\)为新的段数，合并所有儿子容斥后的段数再合并后的段数为k。

那么贡献是\((^{\sum q[y]}_{q[y1],q[y2]，…})*C_{\sum q[y]+1}^{\sum q[y]+1-k}*\prod(-1)^{p[y]-q[y]}*C_{p[y]-1}^{q[y]}\)

那么这个系数是可以预先拆开，然后用背包合并的。

​

Code：

---

#include<bits/stdc++.h> 
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

int mo;

ll ksm(ll x, ll y) {
	ll s = 1;
	for(; y; y /= 2, x = x * x % mo)
		if(y & 1) s = s * x % mo;
	return s;
}

const int N = 5005;

int n, x, y, z;
int fi[N], to[N * 2], nt[N * 2], w[N * 2], tot;

void link(int x, int y, int z) {
	nt[++ tot] = fi[x], to[tot] = y, w[tot] = z, fi[x] = tot;
}

int fa[N], dep[N], d[N];
int siz[N];

ll fac[N], nf[N];
ll f[N], g[N], h[N];

int C(int n, int m) {
	if(n < m) return 0;
	return fac[n] * nf[n - m] % mo * nf[m] % mo;
}

void dg(int x) {
	dep[x] = dep[fa[x]] + 1;
	for(int i = fi[x]; i; i = nt[i]) {
		int y = to[i]; if(y == fa[x]) continue;
		fa[y] = x; d[y] = w[i] / 2;
		dg(y);
	}
	siz[x] = 1;
	fo(i, 0, n) g[i] = 0; g[1] = 1;
	for(int i = fi[x]; i; i = nt[i]) {
		int y = to[i]; if(y == fa[x]) continue;
		{
			fo(i, 0, siz[x]) h[i] = g[i], g[i] = 0;
			fo(i, 1, siz[x]) {
				fo(j, 1, d[y]) {
					ll xs = ((d[y] - j) % 2 ? -1 : 1) * C(d[y] - 1, d[y] - j) * f[y] % mo * d[y] % mo * nf[j] % mo;
					g[i + j] = (g[i + j] + h[i] * xs) % mo;
				}
			}
			siz[x] += siz[y];
		}
	}
	f[x] = 0;
	fo(j, max(1, d[x]), siz[x]) {
		f[x] = (f[x] + g[j] * fac[j - 1] % mo * C(j, j - d[x])) % mo;
	}
	f[x] = (f[x] % mo + mo) % mo;
}


int main() {
	freopen("permutation.in", "r", stdin);
	freopen("permutation.out", "w", stdout);
	scanf("%d %d", &n, &mo);
	fo(i, 1, n - 1) {
		scanf("%d %d %d", &x, &y, &z);
		link(x, y, z); link(y, x, z);
		if(z % 2 == 1) {
			pp("0\n"); return 0;
		}
	}
	if(n == 1) {
		pp("1\n");
		return 0;
	}
	fac[0] = 1; fo(i, 1, n) fac[i] = fac[i - 1] * i % mo;
	fo(i, 0, n) nf[i] = ksm(fac[i], mo - 2);
	dg(1);
	ll ans = f[1];
	ans = ans * n % mo;
	pp("%lld\n", ans);
}