P11363 [NOIP2024] 树的遍历

题目链接：https://www.luogu.com.cn/problem/P11363

题目大意

给定一个 \(n\) 点的树，将树的每条边看做一个新点，将所有相邻的边对应的新点之间连边，得到一个新图。现在给你 \(k\) 条关键边，可以从每条关键边对应的新点开始 DFS 遍历新图，问能得到多少种不同的 DFS 树（无根树，不区分方向）。

Solution 1

先考虑 \(k = 1\) 的做法。此时我们已经确定了起始点，只需要按顺序依次遍历所有点即可。答案为 \(\displaystyle \prod (d_i - 1)!\)，\(d_i\) 为原树上节点的度数。

\(k > 1\) 时，从不同的边开始可能会生成相同的树。接下来考虑在何种情况下会生成相同的树。

换个角度，对每棵形态确定的树，思考从哪些边开始可以生成它。

上图中，蓝色的是原树，红色边是新图中的边，绿色边是新图的某一棵 dfs 树，紫色点是可以生成这棵 dfs 树的边。

注意到每个点相连的所有边对应的点在新图中构成一个完全图，dfs 的过程实际上是从一个点出发不重复地遍历所有完全图中的点，然后从一个点出去。过程中可能会随时走完整个子树方向，然后退回来继续走完全图。

其实只有进入完全图的新点和最后走出完全图的这个新点及其子树内的新点有可能遍历得到这棵树。因为我们在完全图中走的路径是一条链，而从其他点开始走都只能走向链的一边导致生成错误的树。

于是我们可以发现一个结论：可能生成这棵 dfs 树的边一定恰好是一条从原树的叶子到叶子的链。

每棵树都有一条这样的链。我们可以根据链的形态来统计答案。

链上的每个点（原树上的点）下一步走到的点都已经确定了，所以不会产生贡献。而不在链上的点仍能任意走动。

当链确定时，对应的 dfs 树个数即为：

\[\prod_{u \in \{1, 2, \cdots, n\}} (d_u - 1)! \times \prod_{u \in \text{chain}} (d_u - 1)^{-1}. \]

\(\text{chain}\) 表示链上的新点构成的集合。

式子的实际意义是，从一个链上的新点 \(u'\) 走向链上的新点 \(v'\) 过程中，要在完全图中走一条链，所以走向新点 \(v'\) 的这一步只能留到最后走，于是少了一个 \(d_u - 1\) 的贡献。

问题转化为：有一棵树，边有 \(0/1\) 权值，点有点权，求所有叶子到叶子的链，满足这条链上至少有一条 \(1\) 边，点权的乘积的和是多少。（此处的 \(1\) 边就是题面中给的关键边）

\(n=2\) 的情况需要特判一下，否则取一个非叶子节点 \(rt\) 当做根，dfs 一遍，记录每个节点的子树内，叶子到它有 \(1\) / 没有一个 \(1\) 的乘积总和 \(sum_{u, 1/0}\)，计算对答案的贡献即可。

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

#define int long long
const int N = 1e5 + 5, mod = 1e9 + 7;

int n, k, u[N], v[N], fac[N], ans, ed, deg[N], val[N], f[N][2], tot, head[N];
bool tag[N];

struct edge
{
	int to, nxt, id;
} e[N << 2];

void addedge(int u, int v, int w)
{
	e[++tot] = {v, head[u], w};
	head[u] = tot;
}

inline int ksm(int x, int y)
{
	if(x == 0) return 1;
	int res = 1;
	while(y)
	{
		if(y & 1) res = res * x % mod;
		y >>= 1, x = x * x % mod;
	}
	return res;
}

void dfs(int u, int fa)
{
	f[u][0] = f[u][1] = 0;
	int vr = 0;
	for(int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v, u);
		if(tag[e[i].id]) f[v][1] += f[v][0], f[v][1] %= mod, f[v][0] = 0;
		vr += (f[v][1] * (f[u][0] + f[u][1]) % mod + f[v][0] * f[u][1] % mod) % mod;
		vr %= mod;
		f[u][0] += f[v][0]; f[u][0] %= mod;
		f[u][1] += f[v][1]; f[u][1] %= mod;
	}
	ans = (ans + vr * val[u] % mod) % mod;
	if(deg[u] == 1) f[u][0]++;
	f[u][0] = f[u][0] * val[u] % mod;
	f[u][1] = f[u][1] * val[u] % mod;
	return;
}

void solve()
{
	cin >> n >> k;
	fac[0] = 1; ans = 0;
	for(int i = 1; i <= n; i++) tag[i] = 0;
	tot = 0;
	for(int i = 1; i <= n; i++)
		deg[i] = 0, fac[i] = fac[i - 1] * i % mod, head[i] = 0;
	for(int i = 1; i < n; i++)
	{
		cin >> u[i] >> v[i];
		addedge(u[i], v[i], i);
		addedge(v[i], u[i], i);
		deg[u[i]]++, deg[v[i]]++;
	}
	int st = 1;
	for(int i = 1; i <= n; i++)
	{
		st = st * fac[deg[i] - 1] % mod;
		val[i] = ksm(deg[i] - 1, mod - 2);
	}
	for(int i = 1; i <= k; i++)
		cin >> ed, tag[ed] = 1;
	if(n == 2) return (void) (cout << 1 << '\n');
	int root = 0;
	for(int i = 1; i <= n; i++)
		if(deg[i] != 1) {root = i; break;}
	dfs(root, 0);
	for(int i = 1; i <= n; i++)
		ans = ans * fac[deg[i] - 1] % mod;
	cout << ans << '\n';
	return;
}

signed main()
{
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int c, t; cin >> c >> t;
	while(t--) solve();
	return 0;
}