赛前练习。 容斥+树形DP。但是一开始想 DP 是\(O(n^3)\)的，于是想用 NTT 优化成\(O(n^2logn)\)，但是还是 T 了。上海站
沈阳站
[L]
分析：
后来看题解，发现没有注意到转移时只需要枚举到 siz[u]/2 或者 siz[v]/2；而这样枚举的话直接 DP 即可，因为考虑它枚举的过程，会发现大约等价于枚举树上所有的两个点的点对（说大约是因为这里 siz 还除以 2 了），也就是复杂度总体是 \(O(n^2)\) 的。这个想法之前见过，感觉很妙，这里就用上了。
还试图这样减小 NTT 每轮的 \(lim\) ，结果一直 WA 在第 8 个点，百思不得其解。后来调来调去，发现 \(lim \geq siz[u]+siz[v]\) 会 WA，但是改成 \(lim \geq siz[u]/2\) 就是意料之中的 T 了。感觉是因为随意增大 \(lim\) 会出问题，下标超限什么的（比如最后一步这样求和已经大于 \(n\) 了）。以后写 NTT 时得注意精确地赋值 \(lim\) 。代码如下
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=4005,mod=998244353,xn=(1<<13);
int n,fa[N],hd[N],to[N<<1],nxt[N<<1],cnt,siz[N];
int rev[xn];
ll A[xn],B[xn];
ll dp[N][N][3],fac[N],inv[N],inv2[N];
int upt(ll x){while(x>=mod)x-=mod; while(x<0)x+=mod; return x;}
ll pw(ll x,int y)
{
ll ret=1;
for(;y;y>>=1,x=(x*x)%mod) if(y&1)ret=(ret*x)%mod;
return ret;
}
void Init()
{
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=(ll)fac[i-1]*i%mod;
inv[n]=pw(fac[n],mod-2);
for(int i=n-1;i>=0;i--) inv[i]=(ll)inv[i+1]*(i+1)%mod;
int nw=1;
for(int i=1;i<=n;i++) nw=upt(nw*2);
inv2[n]=pw(nw,mod-2);
for(int i=n-1;i>=0;i--) inv2[i]=upt(inv2[i+1]*2);
}
void ntt(ll *a,int tp,int lim)
{
for(int i=0;i<lim;i++)
if(i<rev[i])swap(a[i],a[rev[i]]);
for(int mid=1;mid<lim;mid<<=1)
{
int wn=pw(3,tp==1?(mod-1)/(mid<<1):(mod-1)-(mod-1)/(mid<<1));
for(int j=0,len=(mid<<1);j<lim;j+=len)
for(int k=0,w=1;k<mid;k++,w=(ll)w*wn%mod)
{
int x=a[j+k],y=(ll)w*a[j+mid+k]%mod;
a[j+k]=upt(x+y); a[j+mid+k]=upt(x-y);
}
}
if(tp==1)return; int inv=pw(lim,mod-2);
for(int i=0;i<lim;i++)a[i]=(ll)a[i]*inv%mod;
}
void add(int x,int y){to[++cnt]=y; nxt[cnt]=hd[x]; hd[x]=cnt;}
ll g[xn][3];
void dfs(int u)
{
// printf("u=%d\n",u);
dp[u][0][0]=1; siz[u]=1;
for(int i=hd[u],v;i;i=nxt[i])
{
if((v=to[i])==fa[u])continue;
fa[v]=u; dfs(v); siz[u]+=siz[v];
int lim=1; int L=0;
while(lim<=siz[u]/2) lim<<=1,L++; // siz[u]/2 (若写成siz[u]+siz[v]则WA on test8)
for(int i=0;i<lim;i++) rev[i]=((rev[i>>1]>>1)|((i&1)<<(L-1)));
// TLE
// memset(g,0,sizeof g);
// for(int j=0;j<=siz[u]/2;j++)
// for(int k=0;k<=j&&k<=siz[v]/2;k++)
// g[j][0]=(g[j][0]+dp[u][j-k][1]*(dp[v][k][0]+dp[v][k][1]))%mod;
// for(int j=0;j<=siz[u]/2;j++) dp[u][j][1]=g[j][0];
// for(int j=0;j<=siz[u]/2;j++)
// for(int k=0;k<=j&&k<=siz[v]/2;k++)
// g[j][1]=(g[j][1]+dp[u][j-k][0]*dp[v][k][0])%mod;
// for(int j=1;j<=siz[u]/2;j++) dp[u][j][1]=upt(dp[u][j][1]+g[j-1][1]);
// for(int j=0;j<=siz[u]/2;j++)
// for(int k=0;k<=j&&k<=siz[v]/2;k++)
// g[j][2]=(g[j][2]+dp[u][j-k][0]*(dp[v][k][0]+dp[v][k][1]))%mod;
// for(int j=0;j<=siz[u]/2;j++) dp[u][j][0]=g[j][2];
//约等价于上面写法，TLE，无法避免的多余时间在于dp[v]可转移的仅有siz[v]/2个，而这里扩充成siz[u]/2个
for(int j=0;j<lim;j++) A[j]=dp[u][j][1], B[j]=upt(dp[v][j][0]+dp[v][j][1]);
ntt(A,1,lim); ntt(B,1,lim);
for(int j=0;j<lim;j++) A[j]=(ll)A[j]*B[j]%mod;
ntt(A,-1,lim);
for(int k=0;k<lim;k++) dp[u][k][1]=A[k];
for(int j=0;j<lim;j++) A[j]=dp[u][j][0], B[j]=dp[v][j][0];
ntt(A,1,lim); ntt(B,1,lim);
for(int j=0;j<lim;j++) A[j]=(ll)A[j]*B[j]%mod;
ntt(A,-1,lim);
for(int k=1;k<=lim;k++) dp[u][k][1]=upt(dp[u][k][1]+A[k-1]);
for(int j=0;j<lim;j++) A[j]=dp[u][j][0], B[j]=upt(dp[v][j][0]+dp[v][j][1]);
ntt(A,1,lim); ntt(B,1,lim);
for(int j=0;j<lim;j++) A[j]=(ll)A[j]*B[j]%mod;
ntt(A,-1,lim);
for(int k=0;k<lim;k++) dp[u][k][0]=A[k];
}
}
void dfs2(int u)
{
dp[u][0][0]=1; siz[u]=1;
for(int i=hd[u],v;i;i=nxt[i])
{
if((v=to[i])==fa[u])continue;
fa[v]=u; dfs2(v);
/* TLE
siz[u]+=siz[v];
memset(g,0,sizeof(g));
for(int j=0;j<=siz[u]/2;j++)
{
g[j][0]=dp[u][j][0], g[j][1]=dp[u][j][1];
dp[u][j][0]=0; dp[u][j][1]=0;
}
for(int k=0;k<=siz[u]/2;k++)
{
for(int j=0;j<=siz[v]/2&&j<=k;j++)
{
// dp[u][k][0]=upt(dp[u][k][0] + g[k-j][0]*(dp[v][j][0]+dp[v][j][1])%mod);
// dp[u][k][1]=upt(dp[u][k][1] + g[k-j][1]*(dp[v][j][0]+dp[v][j][1])%mod);
// if(k-1-j>=0)dp[u][k][1]=upt(dp[u][k][1] + g[k-1-j][0]*dp[v][j][0]%mod);
dp[u][k][0] += g[k-j][0]*(dp[v][j][0]+dp[v][j][1]);
dp[u][k][1] += g[k-j][1]*(dp[v][j][0]+dp[v][j][1]);
if(k-1-j>=0) dp[u][k][1] += g[k-1-j][0]*dp[v][j][0];
dp[u][k][0]%=mod; dp[u][k][1]%=mod;
}
}
*/
//(AC) 此做法的复杂度为n^2，相当于枚举点对
memset(g,0,sizeof g);
for(int j=0;j<=siz[u]/2;j++){
for(int k=0;k<=siz[v]/2;k++){
g[j+k][0] += dp[u][j][0]*(dp[v][k][0]+dp[v][k][1]);
g[j+k][1] += dp[u][j][1]*(dp[v][k][0]+dp[v][k][1]);
g[j+k+1][1] += dp[u][j][0]*dp[v][k][0];
g[j+k][0] %= mod,g[j+k][1] %= mod,g[j+k+1][1] %= mod;
}
}
siz[u] = siz[u] + siz[v];
for(int j=0;j<=siz[u]/2+1;j++)
dp[u][j][0] = g[j][0],dp[u][j][1] = g[j][1];
}
}
int cal(int m){return ((ll)fac[m]*inv[m/2]%mod)*(ll)inv2[m/2]%mod;}
ll C(int n,int m){return (ll)fac[n]*fac[m]%mod*fac[n-m]%mod;}
int main()
{
// freopen("data2.txt","r",stdin);
scanf("%d",&n); n<<=1; //n个点
Init();
for(int i=1,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
dfs2(1);
// for(int k=0;k<n;k++)printf("dp[1][%d][0]=%lld, dp[1][%d][1]=%lld\n",k,dp[1][k][0],k,dp[1][k][1]);
ll ans=0;
for(int i=0,f=1;i<=n;i++,f*=(-1))
ans = ((ans + (ll)f*(dp[1][i][0]+dp[1][i][1])%mod*(ll)cal(n-2*i)%mod)%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}
/*
2
1 2
1 3
3 4
3
1 2
2 3
3 4
4 5
5 6
*/