P11363 [NOIP2024] 树的遍历

做了 4h 才做完，交上去还 T 了一发，没救了。

题意

给一棵树，用这棵树建立一张新图 \(G\)，树上的每条边变成 \(G\) 的一个节点，边 \((u,v)\) 存在当且仅当 \(u\) 和 \(v\) 在树上对应的边有公共端点，再给定若干关键点，求 \(G\) 有多少棵生成树 \(T\)，满足存在一个关键边，使得从它开始搜出来的 DFS 生成树可以是 \(T\)。\(n\le10^5\)。

题解

显然链的情况答案为 \(1\)。

菊花的情况，\(G\) 是 \(K_{n-1}\)，生成树一定是一条链，方案数为 \((n-3)!(\binom {n-1}2-\binom{n-1-k}2)\)，即链的端点至少有一个是关键边。

因此原树上的每个点 \(i\) 在 \(G\) 上都对应一个 \(K_{deg_i}\)，对于 \(k=1\) 的情况方案数为 \(\prod(deg_i-1)!\)，即遍历每个 \(K_{deg_i}\) 的 DFS 生成树一定是一条链，链的一个端点需要是 \(e_1\) 过来的那个点，另一个端点任取。

于是考虑在原树上做树形 DP，令 \(f_x\) 表示从 \((x,fa_x)\) 开始 DFS \(G\) 在 \(x\) 子树内的部分，形成的 DFS 生成树个数，\(g_x\) 表示关键边在 \(x\) 子树内，或者是 \((x,fa_x)\)，DFS \(G\) 在 \(x\) 子树内的部分，形成的 DFS 生成树个数。

\(f\) 的转移是容易的，类似 \(k=1\)：

\[f_x=(deg_x-2)!\prod_vf_v \]

考虑 \(g\) 的转移。容易想到枚举关键点所在的子树，但这样会在 \(x\) 的链以两个 \((x,son)\) 为端点，且这两个 \(son\) 子树内的生成树都可以从子树内的关键点出发时算重。于是令 \(h_x\) 表示关键边在 \(x\) 子树内，或者是 \((x,fa_x)\)，且得到的生成树也可以是从 \((x,fa_x)\) 出发搜出来的，这样的生成树个数。考虑链的端点，有：

\[h_x=\begin{cases} (deg_x-2)!\sum_vh_v\prod_{i\neq v}f_i&(x,fa_x)\notin e\\ f_x&(x,fa_x)\in e \end{cases} \]

此时再考虑 \(g\) 的转移，容斥掉上面所说的算重的部分，并且当关键边是 \((x,fa_x)\) 时需要加上从 \((x,fa_x)\) 出发，且未被算过的部分：

\[g_x=(deg_x-1)!\sum_vg_v\prod_{i\neq v}f_i-(deg_x-2)!\sum_{u<v}h_uh_v\prod_{i\neq u,i\neq v}f_i+[(x,fa_x)\in e](f_x-h_x) \]

统计答案时，找到一个叶子 \(x\)，令 \((x,fa_x)\) 为根即可。

前缀和优化一下可以做到 \(O(n\log V)\)，其中 \(\log V\) 是求逆元的复杂度。

实现

#include <iostream>
#define int long long
const int N=2e5+5,mod=1e9+7;
int n,K,a[N],p[N],f[N],g[N],h[N],del[N],fa[N],b[N];
std::basic_string<int> G[N];
struct Edge {int u,v;} e[N];
int qpow(int x,int y) {int r=1;for(;y;y>>=1,x=x*x%mod) if(y&1) r=r*x%mod;return r;}
void dfs0(int x,int fa)
{::fa[x]=fa;for(int v:G[x]) if(v!=fa) dfs0(v,x);
}
void dfs(int x,int fa)
{int son=G[x].size()-1,prd=1;for(int v:G[x]) if(v!=fa) dfs(v,x),prd=prd*f[v]%mod;for(int v:G[x]) if(v!=fa) del[v]=qpow(f[v],mod-2);f[x]=p[son]*prd%mod,g[x]=h[x]=0;if(son){for(int v:G[x]) if(v!=fa){(h[x]+=h[v]*prd%mod*del[v])%=mod;(g[x]+=g[v]*prd%mod*del[v])%=mod;}h[x]=h[x]*p[son-1]%mod;g[x]=g[x]*p[son]%mod;}if(son>1){int tmp=0,pre=0;for(int v:G[x]) if(v!=fa)(tmp+=pre*h[v]%mod*del[v]%mod*prd)%=mod,(pre+=h[v]*del[v])%=mod;(g[x]-=tmp*p[son-1])%=mod;}if(b[x]) (g[x]+=f[x]-h[x])%=mod,h[x]=f[x];
}
void neatisaac()
{for(int i=1;i<=n;i++) G[i].clear(),b[i]=0;std::cin>>n>>K;for(int i=1,u,v;i<n;i++) std::cin>>u>>v,G[u]+=v,G[v]+=u,e[i]={u,v};for(int i=1;i<=K;i++) std::cin>>a[i];for(int i=1;i<=n;i++) if(G[i].size()==1){dfs0(i,0);for(int j=1;j<=K;j++)fa[e[a[j]].u]==e[a[j]].v?b[e[a[j]].u]=1:b[e[a[j]].v]=1;dfs(G[i][0],i),std::cout<<(g[G[i][0]]+mod)%mod<<'\n';return;}
}
signed main()
{std::cin.tie(0)->sync_with_stdio(0);int c,T;std::cin>>c>>T;p[0]=1;for(int i=1;i<N;i++) p[i]=p[i-1]*i%mod;while(T--) neatisaac();
}