题解：P11363 [NOIP2024] 树的遍历
喵仔牛奶
·
·
题解
UPD on 2025.9.20：重构全文。
超级简洁的容斥做法。题解较为详细。
Solution
先来观察一下部分分 k\le 2：
-
- 对于 k=2，考虑容斥，求出 e_1 出发和 e_2 出发的答案，再减去从两者出发都可以得到的答案。两者出发都可以得到的答案怎么求呢？把两条边连成一条链，链上的点（不包括端点）进入和出去的边都确定了，这些点只有 (d_i-2)! 种方案。
考虑求 $g(S)$。在原树上，如果以某个点为根有三个子树里有钦定的边，答案为 $0$。原因是这些边必须从开头或结尾走来，三条中必然有一条不行。因此得到本题最关键的结论：**钦定的边必然构成原树上的一条链。**
链上的点（不包括端点）只有 $(d_i-2)!$ 种方案，其他点有 $(d-1)!$ 种方案。记这条链上的点构成的集合（不包括端点）为 $L$，新树的个数为：
$$\prod_{i=1}^{n}(d_i-1)!\times\prod_{i\in L}(d_i-1)^{-1}$$
前面和链无关，可以提出最后乘。记 $i$ 的点权 $c_i=(d_i-1)^{-1}$，记链的贡献为链上点权之积（不包括端点）。求链的贡献和的题，一般的思路是枚举 LCA（也就是链上最浅的点），如果 $x\to y$ 的链 LCA 为 $z$，那么这条链就可以分解为 $z\to x$ 和 $z\to y$ 两条祖先到后代的链。
设 $f_x$ 为 $x$ 子树内的边所有钦定方法（至少钦定一条边）中 $x\to y$ 的贡献和（$y$ 为形成的链的链底，$y$ 不算在链上但 $x$ 算）。转移考虑枚举儿子 $y$，链从 $y$ 过来：
- 若 $(x,y)$ 可以为起点，三种情况：
- 只选 $(x,y)$：链上没有点，贡献为 $-1$；
- 只选 $y$ 子树中的链：枚举从哪个子树来，新增一个点 $x$，贡献为 $c_xf_y$。
- 同时选两者：同上，但是新增一条边系数乘 $-1$，贡献为 $-c_xf_y$。
- 总贡献为 $(-1)+\big(c_i\sum_{y}f_y\big)+\big(-c_i\sum_{y}f_y\big)=-1$。
- 否则，一种情况:
- 只选 $y$ 子树中的链，贡献同上。
- 贡献为 $c_i\sum_{y}f_y$。
- 所有 $y$ 的贡献求和即为 $f_x$。
得到这个之后，我们枚举 LCA 算答案。枚举 $x$ 作为 LCA，分类讨论：
- 如果链形如 $x\to y$（$y$ 在 $x$ 子树内），枚举 $y$。此时 $(x,y)$ 必须被钦定（意味着它必选可以作为起点），讨论是否在 $y$ 子树内钦定边：
- 钦定，算上 $(x,y)$ 对系数的贡献 $-1$，贡献为 $-f_y$。
- 不钦定，链为 $x\to y$，除去端点后没有点，贡献为 $-1$；
- 如果链形如 $y\to z$（$y,z$ 在 $x$ 子树内），枚举 $y,z$：
- 可以发现次数贡献和转移时一样。若 $(x,y)$ 可以为起点则 $w_y=-1$，否则 $w_y=f_y$；若 $(x,z)$ 可以为起点则 $w_z=-1$，否则 $w_z=f_z$。
- 对答案的贡献即为 $w_y\cdot w_z\cdot c_x$。
第二种贡献容易前缀和优化，都来做紫题了想必不需要多说。注意我们算的系数是 $(-1)^{\lvert S\rvert}$，而要算的是 $(-1)^{\lvert S\rvert+1}$，因此答案还需要乘上 $-1$。
线性预处理逆元（不线性也可以），复杂度为 $\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;
}
```