专栏文章

题解：P11363 [NOIP2024] 树的遍历

喵喵仔牛奶
P11363题解参与者 12已保存评论 30

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
30 条
当前快照
1 份
快照标识符
@miqwnu40
此快照首次捕获于
2025/12/04 11:57
3 个月前
此快照最后确认于
2025/12/04 11:57
3 个月前
查看原文
UPD on 2025.9.20：重构全文。
超级简洁的容斥做法。题解较为详细。

Solution

先来观察一下部分分 k≤2k\le 2：
  • k=1k=1 时，考虑对于一个点，它的邻边形成了一条新树上的链。进入它的边确定了，剩下的边的顺序可以随意排列，因此答案为 ∏(di−1)!\prod(d_i-1)!。
  • 对于 k=2k=2，考虑容斥，求出 e1e_1 出发和 e2e_2 出发的答案，再减去从两者出发都可以得到的答案。两者出发都可以得到的答案怎么求呢？把两条边连成一条链，链上的点（不包括端点）进入和出去的边都确定了，这些点只有 (di−2)!(d_i-2)! 种方案。
kk 更大时，仍然考虑容斥。钦定一个边集 SS，设可以同时以这些边为根的新树个数为 g(S)g(S)，答案即为 ∑S⊆{e1,e2,⋯ ,ek}∧S≠∅(−1)∣S∣+1g(S)\sum_{S\subseteq\{e_1,e_2,\cdots,e_k\}\land S\neq\varnothing}(-1)^{\lvert S\rvert+1}g(S)。
考虑求 g(S)g(S)。在原树上，如果以某个点为根有三个子树里有钦定的边，答案为 00。原因是这些边必须从开头或结尾走来，三条中必然有一条不行。因此得到本题最关键的结论：钦定的边必然构成原树上的一条链。
链上的点（不包括端点）只有 (di−2)!(d_i-2)! 种方案，其他点有 (d−1)!(d-1)! 种方案。记这条链上的点构成的集合（不包括端点）为 LL，新树的个数为： ∏i=1n(di−1)!×∏i∈L(di−1)−1\prod_{i=1}^{n}(d_i-1)!\times\prod_{i\in L}(d_i-1)^{-1}
前面和链无关，可以提出最后乘。记 ii 的点权 ci=(di−1)−1c_i=(d_i-1)^{-1}，记链的贡献为链上点权之积（不包括端点）。求链的贡献和的题，一般的思路是枚举 LCA（也就是链上最浅的点），如果 x→yx\to y 的链 LCA 为 zz，那么这条链就可以分解为 z→xz\to x 和 z→yz\to y 两条祖先到后代的链。
设 fxf_x 为 xx 子树内的边所有钦定方法（至少钦定一条边）中 x→yx\to y 的贡献和（yy 为形成的链的链底，yy 不算在链上但 xx 算）。转移考虑枚举儿子 yy，链从 yy 过来：
  • 若 (x,y)(x,y) 可以为起点，三种情况：
    • 只选 (x,y)(x,y)：链上没有点，贡献为 −1-1；
    • 只选 yy 子树中的链：枚举从哪个子树来，新增一个点 xx，贡献为 cxfyc_xf_y。
    • 同时选两者：同上，但是新增一条边系数乘 −1-1，贡献为 −cxfy-c_xf_y。
    • 总贡献为 (−1)+(ci∑yfy)+(−ci∑yfy)=−1(-1)+\big(c_i\sum_{y}f_y\big)+\big(-c_i\sum_{y}f_y\big)=-1。
  • 否则，一种情况:
    • 只选 yy 子树中的链，贡献同上。
    • 贡献为 ci∑yfyc_i\sum_{y}f_y。
  • 所有 yy 的贡献求和即为 fxf_x。
得到这个之后，我们枚举 LCA 算答案。枚举 xx 作为 LCA，分类讨论：
  • 如果链形如 x→yx\to y（yy 在 xx 子树内），枚举 yy。此时 (x,y)(x,y) 必须被钦定（意味着它必选可以作为起点），讨论是否在 yy 子树内钦定边：
    • 钦定，算上 (x,y)(x,y) 对系数的贡献 −1-1，贡献为 −fy-f_y。
    • 不钦定，链为 x→yx\to y，除去端点后没有点，贡献为 −1-1；
  • 如果链形如 y→zy\to z（y,zy,z 在 xx 子树内），枚举 y,zy,z：
    • 可以发现次数贡献和转移时一样。若 (x,y)(x,y) 可以为起点则 wy=−1w_y=-1，否则 wy=fyw_y=f_y；若 (x,z)(x,z) 可以为起点则 wz=−1w_z=-1，否则 wz=fzw_z=f_z。
    • 对答案的贡献即为 wy⋅wz⋅cxw_y\cdot w_z\cdot c_x。
第二种贡献容易前缀和优化，都来做紫题了想必不需要多说。注意我们算的系数是 (−1)∣S∣(-1)^{\lvert S\rvert}，而要算的是 (−1)∣S∣+1(-1)^{\lvert S\rvert+1}，因此答案还需要乘上 −1-1。
线性预处理逆元（不线性也可以），复杂度为 O(Tn)\mathcal O(Tn)。

Code

代码有注释。
CPP
#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define ppc(x) __builtin_popcount(x)
using namespace std;
namespace math { ... } // 自动取模类
namespace Milkcat {
	typedef long long LL;
	typedef pair<int, int> pii;
	const int N = 1e6 + 5, mod = 1e9 + 7;
	typedef math::mint<mod> MI;
	int n, k, x, y, vs[N]; MI rs, f[N], fac[N], inv[N]; vector<pii> G[N];
	void dfs(int x, int fa) {
		MI co = inv[SZ(G[x]) - 1], s = 0, w = 0; // co 是 x 的点权
		for (auto [y, i] : G[x]) { 
			if (y == fa) continue;
			dfs(y, x), w = (vs[i] ? -1 : f[y]);
			f[x] += w * co, rs += s * w * co, s += w; // 转移 f[x]；计算 y->z 的贡献
			if (vs[i]) rs += -f[y] - 1; // x->y 的贡献
		}
	}
	int main() {
		cin >> n >> k, rs = 0;
		REP(i, 1, n - 1)
			cin >> x >> y, G[x].pb(y, i), G[y].pb(x, i);
		REP(i, 1, k) cin >> x, vs[x] = 1;
		fac[0] = inv[0] = 1;
		REP(i, 1, n) {
			fac[i] = fac[i - 1] * i;
			inv[i] = (i > 1 ? inv[mod % i] * (mod - mod / i) : 1); // 预处理逆元
		}
		dfs(1, 0);
		REP(i, 1, n) rs *= fac[SZ(G[i]) - 1];
		cout << -rs << '\n'; // 不要忘记乘上 -1
		REP(i, 1, n) f[i] = vs[i] = 0, G[i].clear();
		return 0;
	}
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int C, T = 1; cin >> C >> T;
	while (T --) Milkcat::main();
	return 0;
}

评论

共 30 条评论，欢迎与作者交流。

正在加载评论...