首先转化题意,对于确定的两棵树,设它们的边集分别为
op=0
这是最简单的一种情况,因为两棵树的形态已知,所以只有一种方案。枚举
op=1
我们不妨认为
然而
代回答案式并交换求和号,得
到此为止式子已经很简洁了,关键在于
对于一个
n 个点、k 个连通块的森林,每个连通块的大小分别为a_1,a_2,\cdots,a_k ,将其连成一棵树的方案共有h(n,k)=n^{k-2}\prod\limits_{i=1}^{k} a_i 种。
下面是一个基于 Prufer 序列的证明:
将每个连通块视为一个点,考虑它们之间连成的树。容易发现在连通块
u,v 间连边的贡献为a_ua_v ,因此如果一个编号v 在 Prufer 序列中出现了i 次(即度数为i+1 ),则它对答案的贡献为a_v^{i+1} 。考虑到每个节点的原标号是不同的,我们设贡献的 EGF 为F_v(x) ,那么F_v(x)=\sum_{i=0}^{k-1}a_v^{i+1}\frac{x^i}{i!}=a_v e^{a_vx}
\begin{aligned}h(n,k)&=(k-2)![x^{k-2}]\prod_{i=1}^{k} F_i(x)\\&=(k-2)![x^{k-2}]\prod_{i=1}^k a_i e^{a_ix}\\&=(k-2)![x^{k-2}]e^{nx}\prod_{i=1}^k a_i\\&=n^{k-2}\prod_{i=1}^{k}a_i\end{aligned}
也可以用矩阵树定理手解行列式来求证。
回到题目,根据定义,容易看出
这个式子就具有一些意义了。我们不妨设
我们想办法对 DP 的状态进行一些优化以降低复杂度。考虑去掉第二维,发现仍可以通过某些方法计算贡献。具体地,我们利用每个贡献的组合意义,在当前连通块中加入一个点相当于将答案加上
答案即为
op=2
与上一问类似,我们写出容斥的式子:
其实唯一的区别就是把
这是因为大小为
所以写一个多项式 exp 然后取第
这道题有个需要注意的地方就是
#include <cstdio>
#include <vector>
#include <set>
using namespace std;
const int P=998244353;
int qpow(int n, int k)
{
int r=1;
while (k)
{
if (k&1) r=1ll*r*n%P;
n=1ll*n*n%P, k>>=1;
}
return r;
}
int n, y, op;
namespace Solver1
{
void main()
{
set<pair<int, int>> edges;
for (int i=1, u, v; i<n; i++)
{
scanf("%d%d", &u, &v);
if (u>v) swap(u, v);
edges.insert(make_pair(u, v));
}
int cnt=n;
for (int i=1, u, v; i<n; i++)
{
scanf("%d%d", &u, &v);
if (u>v) swap(u, v);
if (edges.count(make_pair(u, v))) cnt--;
}
printf("%d\n", qpow(y, cnt));
}
}
namespace Solver2
{
const int MAXN=100005;
vector<int> G[MAXN];
int K, f[MAXN], g[MAXN];
void DFS(int u, int fa)
{
f[u]=K, g[u]=1;
for (int v: G[u]) if (v!=fa)
{
DFS(v, u);
f[u]=(1ll*f[u]*f[v]+1ll*f[u]*g[v]+1ll*g[u]*f[v])%P;
g[u]=(1ll*g[u]*f[v]+1ll*g[u]*g[v])%P;
}
}
void main()
{
if (y==1) return printf("%d\n", qpow(n, n-2)), void();
for (int i=1, u, v; i<n; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
K=1ll*n*y%P*qpow(1-y+P, P-2)%P, DFS(1, 0);
printf("%lld\n", 1ll*f[1]*qpow(1-y+P, n)%P*qpow(n, P-3)%P);
}
}
namespace Solver3
{
const int MAXN=1<<18;
/* poly templates begin */
/* poly templates end */
int fac[MAXN], ifac[MAXN];
int a[MAXN], b[MAXN];
void main()
{
if (y==1) return printf("%d\n", qpow(n, 2*(n-2))), void();
fac[0]=1;
for (int i=1; i<=n; i++) fac[i]=1ll*fac[i-1]*i%P;
ifac[n]=qpow(fac[n], P-2);
for (int i=n; i>=1; i--) ifac[i-1]=1ll*ifac[i]*i%P;
int K=1ll*n*n%P*y%P*qpow(1-y+P, P-2)%P;
for (int i=1; i<=n; i++) a[i]=1ll*K*qpow(i, i)%P*ifac[i]%P;
poly_exp(a, b, n+1);
printf("%lld\n", 1ll*b[n]*fac[n]%P*qpow(1-y+P, n)%P*qpow(n, P-5)%P);
}
}
int main()
{
// freopen("P5206.in", "r", stdin);
// freopen("P5206.out", "w", stdout);
scanf("%d%d%d", &n, &y, &op);
if (op==0) Solver1::main();
else if (op==1) Solver2::main();
else Solver3::main();
return 0;
}