#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
int n;
vector<int> e[3010];
ll dp[3100][3010][2],f[3010],fi[3010],g[3010][2],tot[3010],tt[3010],sz[3010];
//dp[x][i][0/1]表示以X为根的子树中x的排名为i，0/1 表示排名比周围节点 后/前
ll qpow(ll a,ll b){
	ll ans=1;
	for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;
	return ans; 
}
ll C(int n,int m){
	if(n<m)return 0;
	return f[n]*fi[m]%mod*fi[n-m]%mod;
}
void dfs(int x,int xfa){
	sz[x]=1;//初始化 
	dp[x][1][0]=dp[x][1][1]=1;
	for(int y:e[x])if(y!=xfa){
		dfs(y,x);
		for(int i=1;i<=sz[y];i++)tot[i]=(tot[i-1]+dp[y][i][0])%mod;//记录前缀和 
		tt[sz[y]+1]=0;
		for(int i=sz[y];i;i--)tt[i]=(tt[i+1]+dp[y][i][1])%mod;
		for(int i=1;i<=sz[x];i++){
			for(int j=0;j<=sz[y];j++){
				//将以y为根的子树中取j个节点的排名在x排名之前 
				g[i+j][1]=(g[i+j][1]+C(i-1+j,j)*C(sz[x]+sz[y]-i-j,sz[y]-j)%mod*dp[x][i][1]%mod*tot[j]/*此时y的排名要在x前，所以y的排名要小于等于x*/%mod)%mod;
				g[i+j][0]=(g[i+j][0]+C(i-1+j,j)*C(sz[x]+sz[y]-i-j,sz[y]-j)%mod*dp[x][i][0]%mod*tt[j+1]/*此时y的排名要在x后，所以y的排名要大于x*/%mod)%mod;
			}
		}
		sz[x]+=sz[y];
		for(int i=0;i<=sz[x];i++){
			dp[x][i][0]=g[i][0];dp[x][i][1]=g[i][1];
			g[i][0]=g[i][1]=0;
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	f[0]=1;
	fi[0]=1;
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]*i%mod;
		fi[i]=qpow(f[i],mod-2);
	}
	dfs(1,0);
	ll ans=0;
	for(int i=1;i<=n;i++){
		ans=(ans+dp[1][i][0])%mod;
		ans=(ans+dp[1][i][1])%mod;
	}
	cout<<ans;
	return 0;
}

可能更好的阅读体验

题目链接
考虑这棵树在满足条件下是什么样子的？

我们发现如果对于一棵树黑白染色，黑色表示周围的点大于自身，白色的点反之，是满足条件的。同时，将黑白点反色也是满足条件的。

我们考虑进行 $\text{dp}$，设 $dp_{i,j,0/1}$ 表示以点 $i$ 为根的子树，$i$ 点权值的排名是 $j$，且 $i$ 点颜色是黑或白的方案数。

以 $x$ 点为白点为例，考虑将子树 $v$ 合并到 $x$ 的过程中前 $t$ 个点插入到了 $x$ 前，剩余的 $sz[v] - t$ 个点在 $x$ 后。那么此时转移为

$$dp[x][i+t][1] += \binom{i-1+t}{t} \binom{sz[x]-i+sz[v]-t}{sz[v]-t} \times dp[x][i][1] \times dp[v][j][0](t \geq j)$$

对于 $x$ 点是黑点的转移同理为

$$dp[x][i+t][0] += \binom{i-1+t}{t} \binom{sz[x]-i+sz[v]-t}{sz[v]-t} \times dp[x][i][0] \times dp[v][j][1] (t \leq j-1)$$

此时 $dp$ 的转移复杂度为 $O(n^3)$，无法通过。

考虑枚举 $t$ 算所有能转移到 $t$ 的 $j$ 的贡献，式子改写为

$$dp[x][i+j][1] += \binom{i-1+j}{j} \binom{sz[x]-i+sz[v]-j}{sz[v]-j} \times dp[x][i][1] \times pre[j]$$$$dp[x][i+j][0] += \binom{i-1+j}{j} \binom{sz[x]-i+sz[v]-j}{sz[v]-j} \times dp[x][i][0] \times suc[j+1]$$

其中

$$pre[j]= \sum_{k=1}^{j} dp[v][k][0]$$ $$suc[j]= \sum_{k=j+1}^{sz[v]} dp[v][k][1]$$

复杂度为 $O(n^2)$，可以通过。

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int N=3005;
struct node{
	int nxt;int to;
}e[N*2];
int head[N],tot;
int n,rx,ry;
int fa[N],sz[N];
int dp[N][N][2],pre[N],suc[N];
int g[N][2],ans;
int fac[N],ifac[N];
inline void read(int &x) 
{
	int f=1;char c;
	for(x=0,c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); x*=f;
} 
inline int mn(int _x,int _y){return _x<_y?_x:_y;}
inline int mx(int _x,int _y){return _x>_y?_x:_y;}
inline int ab(int _x){return _x<0?-_x:_x;}
inline void add(int from,int to){
	e[++tot].to=to;e[tot].nxt=head[from];head[from]=tot;
}
inline int C(int n,int m){
	if(n<m) return 0;
	return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
inline int qpow(int base,int cnt){
	int rest=1;
	while(cnt){
		if(cnt&1) rest=1ll*rest*base%mod;
		base=1ll*base*base%mod;
		cnt>>=1;
	}
	return rest;
}
inline void dfs(int x){
	sz[x]=1;
	dp[x][1][0]=dp[x][1][1]=1;
	for(int ei=head[x];ei;ei=e[ei].nxt){
		int v=e[ei].to;
		if(v==fa[x]) continue;
		fa[v]=x;dfs(v);
		for(int j=0;j<=sz[v]+1;j++) pre[j]=suc[j]=0;
		for(int j=1;j<=sz[v];j++) pre[j]=(pre[j-1]+dp[v][j][0])%mod;
		for(int j=sz[v];j>=1;j--) suc[j]=(suc[j+1]+dp[v][j][1])%mod;
		for(int i=1;i<=sz[x];i++){
			for(int j=0;j<=sz[v];j++){
            	//dp
				g[i+j][0]=(g[i+j][0]+1ll*C(i-1+j,j)*C(sz[x]-i+sz[v]-j,sz[v]-j)%mod*dp[x][i][0]%mod*suc[j+1]%mod)%mod;
				g[i+j][1]=(g[i+j][1]+1ll*C(i-1+j,j)*C(sz[x]-i+sz[v]-j,sz[v]-j)%mod*dp[x][i][1]%mod*pre[j]%mod)%mod;
			}
		}
		sz[x]+=sz[v];
		for(int i=0;i<=sz[x];i++){
			dp[x][i][0]=g[i][0];dp[x][i][1]=g[i][1];
			g[i][0]=g[i][1]=0;
		}
	}
//	for(int i=1;i<=sz[x];i++) printf("dp[%d][%d] [0]=%d [1]=%d\n",x,i,dp[x][i][0],dp[x][i][1]);
	return ;
}
int main()
{
	read(n);
	for(int i=1;i<n;i++){
		read(rx);read(ry);
		add(rx,ry);add(ry,rx);
	}
	fac[0]=1;for(int i=1;i<=n+1;i++) fac[i]=1ll*i*fac[i-1]%mod;
	ifac[n+1]=qpow(fac[n+1],mod-2);
	for(int i=n;i>=0;i--) ifac[i]=1ll*(i+1)*ifac[i+1]%mod;

	dfs(1);
	for(int i=1;i<=n;i++){//枚举根节点的排名并累加答案
		ans=(ans+dp[1][i][0])%mod;
		ans=(ans+dp[1][i][1])%mod;
	}
	printf("%d\n",ans);
	return 0;
}