不错的一道 Combinatorics。
结论 1： \(n\) 为奇数时答案为 \(0\)。
设 \(d_i\) 为与点 \(i\) 相连的边边权乘积。每加入一条边对两端的 \(d_i\) 贡献乘积为 \(-1\)，因此 \(\prod d_i = 1\)。当 \(n\) 为奇数时要求 \(\prod d_i = -1\)，不合法。
结论 2： 树的形态确定后，合法的填边权方案只有一种。
考虑从叶子开始自底向上，显然可以依次确定边权。
结论 3： 若一条边两端点连接的子树大小为奇数，则边权为 \(-1\)，否则为 \(1\)。
仍然考虑自底向上归纳证明。对于连接叶子的边显然满足。设当前非叶子结点为点 \(u\)，如果连向儿子的边中有奇数条是 \(-1\)，那么说明 \(sz_u\) 为偶数，并且 \(u \to fa_u\) 的边权为 \(1\)。反之说明 \(sz_u\) 为奇数，并且 \(u \to fa_u\) 的边权为 \(-1\)。
考虑枚举 \(1 \to n\) 路径上的每条边算贡献。枚举 \(1\) 所在子树的点数 \(i\)，则 \(n\) 所在子树点数为 \(n - i\)。边权可以由 \(i\) 的奇偶性确定，考虑算方案数。从两棵子树分别拎出一个根，再从剩下 \(n - 2\) 个点选 \(i - 1\) 个点作为 \(1\) 所在子树。最后根据题目给出的公式得出 \(n\) 个点的有标号无根树数量为 \(n^{n-2}\)，可得方案数为 \(i^{i-1}(n-i)^{n-i-1}\binom{n-2}{i-1}\)。
code
/*
p_b_p_b txdy
AThousandSuns txdy
Wu_Ren txdy
Appleblue17 txdy
*/
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 500100;
const ll mod = 998244353;
ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, fac[maxn], ifac[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld", &n);
if (n & 1) {
puts("0");
return;
}
fac[0] = 1;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n] = qpow(fac[n], mod - 2);
for (int i = n - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
ll ans = 0;
for (int i = 1; i < n; ++i) {
ans = (ans + ((i & 1) ? mod - 1 : 1LL) * qpow(i, i - 1) % mod * qpow(n - i, n - i - 1) % mod * C(n - 2, i - 1) % mod) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}