GYM104373H Permutation on Tree 题解

First Post:

Last Update:

我比 做法少了一步，十分可惜。

考虑直接枚举最终排列中相邻的两个点 ，怎么算贡献。

设 。

我们考虑如何造出一棵点数为 的新树，使得 被捆绑成一个点，同时满足之前的限制。

因为树的拓扑序个数是 ，我们只需关注这个过程中 的变化即可。

对于 以及 的祖先，它们的 只是减少了 ，这部分变化可以提前预处理，设为 。

接下来考虑 到 的这条链。我们尝试把 到 与 到 这两条链归并为一条新链，然后处理新链上的点 的变化。

那么设 表示 到 这条链所有归并方式的贡献系数之和。（不考虑 和 本身的 变化）

那么 可以从 转移，表示在新链末端放一个 ，那么此时， 在新链上的 会变成 (这里的 数组是原树的 )，所以转移系数是 。从 的转移是同理的。

那么一对 的贡献就是 。

注意特判 是 的儿子和 是 的兄弟的情况。

DP 初值和转移顺序不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5,P = 1e9 + 7,Lg = 12;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) {if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int n,rt;
vector<int> G[N];
int sze[N];
int fac[N],ifac[N],inv[N];
inline void init(int n) {
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[1] = 1;
	for(int i = 2;i <= n;i++) inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
	ifac[0] = 1;
	for(int i = 1;i <= n;i++) ifac[i] = 1ll * ifac[i - 1] * inv[i] % P;
}
inline int C(int n,int m) { if(n < 0 || m < 0 || n < m) return 0;return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % P;}
int mdp[N];

int ST[Lg][N],lg[N],dfn[N],dep[N],fa[N];
void dfs0(int x,int f) {
	sze[x] = 1;ST[0][dfn[x] = ++dfn[0]] = f;
	dep[x] = dep[f] + 1;
	for(auto y : G[x])
		if(y != f) fa[y] = x,dfs0(y,x),sze[x] += sze[y];
}	
int Min(int x,int y) { return dfn[x] < dfn[y] ? x : y;}
void init_lca() {
	lg[0] = -1;dfs0(rt,0);
	for(int i = 1;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	for(int j = 1;j < Lg;j++)
		for(int i = 1;i + (1 << j) - 1 <= n;i++)
			ST[j][i] = Min(ST[j - 1][i],ST[j - 1][i + (1 << j - 1)]);
}
void dfs1(int x) {
	if(x == rt) mdp[x] = 1ll * sze[x] * inv[sze[x] - 1] % P;
	else mdp[x] = 1ll * mdp[fa[x]] * sze[x] % P * inv[sze[x] - 1] % P;
	for(auto y : G[x])
		if(y != fa[x]) dfs1(y);
}
int lca(int x,int y) {
	if(x == y) return x;
	x = dfn[x];y = dfn[y];
	if(x > y) swap(x,y);
	int k = lg[y - (x++)];
	return Min(ST[k][x],ST[k][y-(1<<k)+1]);
}
int dp[N][N];
int All; // 原树的拓扑序方案
int DP() {
	int ans = 0;
	static vector<pair<int,int> > Ps[N * 2];
	for(int i = 1;i <= n;i++)
		for(int j = i;j <= n;j++) dp[i][j] = dp[j][i] = (fa[i] == fa[j]);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++) {
			if(lca(i,j) == i || lca(i,j) == j || i == j) continue;
			if(dp[i][j] && i < j) {
				int coef = 1ll * All * mdp[lca(i,j)] % P;
				coef = 1ll * coef * sze[i] % P * sze[j] % P * inv[sze[i] + sze[j] - 1] % P;
				Plus(ans,1ll * (coef + coef) * (j - i) % P);
			} 
			else Ps[dep[i] + dep[j]].emplace_back(i,j);
		}
	for(int d = 1;d <= 2 * n;++d) 
		for(auto it : Ps[d]) {
			int x = it.first,y = it.second;
			int fx = fa[x],fy = fa[y];
			Plus(dp[x][y],1ll * dp[fx][y] * sze[fx] % P * inv[sze[fx] + sze[y] - 1] % P);
			Plus(dp[x][y],1ll * dp[x][fy] * sze[fy] % P * inv[sze[fy] + sze[x] - 1] % P);
			if(x >= y) continue;
			int coef = 1ll * All * mdp[lca(x,y)] % P;
			coef = 1ll * coef * sze[x] % P * sze[y] % P * inv[sze[x] + sze[y] - 1] % P;
			coef = 1ll * coef * dp[x][y] % P;
			Plus(ans,1ll * (coef + coef) * (y - x) % P);
		}
	return ans;
}
int main() {
	cin >> n >> rt;
	for(int i = 1,u,v;i < n;i++)
		cin >> u >> v,G[u].push_back(v),G[v].push_back(u);
	init(n);
	init_lca();
	dfs1(rt);
	All = fac[n - 1];
	for(int i = 1;i <= n;i++) All = 1ll * All * inv[sze[i]] % P;
	int ans = 0;
	for(int i = 1;i <= n;i++)
		for(auto j : G[i]) if(j != fa[i]) {
			int coef = 1ll * All * mdp[i] % P * sze[j] % P;
			Plus(ans,1ll * coef * abs(j - i) % P);
		}
	Plus(ans,DP());
	cout << ans << endl;
	return 0;
}
≡