河北省建设执业资格中心网站,单职业传奇网站,购物网站后台模板下载,青海制作网站多少钱正题
题面链接:https://www.ybtoj.com.cn/contest/62/problem/3 题目大意 nnn个点的一棵树#xff0c;每个边的边会表示一个大小关系#xff08;如pxpyp_xp_ypxpy或pxpyp_xp_ypxpy#xff09;。求有多少个排列满足所有条件。 解题思路
考…正题
题面链接:https://www.ybtoj.com.cn/contest/62/problem/3 题目大意
nnn个点的一棵树每个边的边会表示一个大小关系如pxpyp_xp_ypxpy或pxpyp_xp_ypxpy。求有多少个排列满足所有条件。 解题思路
考虑树形dpdpdp设fi,jf_{i,j}fi,j表示点iii的子树中有jjj个比他小的数字时的方案数。
那么如果有条件pypxp_yp_xpypx考虑如何转移我们枚举一下i,ji,ji,j表示之前比iii小的数的个数和yyy里面比xxx小的个数然后再枚举一个kkk表示yyy里面比yyy小的数的个数。 然后用组合数插板表示方案发现这样是O(n3)O(n^3)O(n3)的发现kkk可以前/后缀和优化所以可以缩掉时间复杂度为O(n2)O(n^2)O(n2) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5100,XJQ998244353;
struct node{ll to,next,w;
}a[N*2];
ll n,tot,ls[N],c[N][N],f[N][N],g[N],siz[N],ans;
ll C(ll n,ll m){return c[n1][m1];}
void addl(ll x,ll y,ll w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;return;
}
void dfs(ll x,ll fa){f[x][0]1;siz[x]1;for(ll pls[x];p;pa[p].next){ll ya[p].to;if(yfa)continue;dfs(y,x);for(ll i0;isiz[x]siz[y];i)g[i]0;if(a[p].w){for(ll i0;isiz[x];i){ll tmp0;for(ll jsiz[y]-1;j0;j--){ll pxi,pyj;tmp(tmpf[y][j])%XJQ;ll sxsiz[x]-i-1,sysiz[y]-j-1;(g[siz[x]siz[y]-sx-sy-2]f[x][i]*tmp%XJQ*C(sxsy1,sx)%XJQ*C(pxpy,py)%XJQ)%XJQ;}}}else{for(ll i0;isiz[x];i){ll tmp0;for(ll j0;jsiz[y];j){ll pxi,pyj;tmp(tmpf[y][j])%XJQ;ll sxsiz[x]-i-1,sysiz[y]-j-1;(g[pxpy1]f[x][i]*tmp%XJQ*C(pxpy1,px)%XJQ*C(sxsy,sy)%XJQ)%XJQ;}}}siz[x]siz[y];for(ll i0;isiz[x];i)f[x][i]g[i];}return;
}
int main()
{freopen(perm.in,r,stdin);freopen(perm.out,w,stdout);scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y,0);addl(y,x,1);}c[0][0]1;for(ll i1;iN;i)for(ll j1;jN;j)c[i][j](c[i-1][j]c[i-1][j-1])%XJQ;dfs(1,1);for(ll i0;isiz[1];i)(ansf[1][i])%XJQ;printf(%lld\n,ans);
}
