【题意】

题目链接：https://codeforces.com/gym/104076/problem/C
简要题意：给定一棵n个点的有根树，对于所有的二元组(i,j)(i,j)(i,j)求这颗树所有可能的dfs序中有多少个dfs序满足第iii个点出现在dfs序第jjj个位置。

【思路】

赛场上假了无数次以后，我终于才理清楚了这题的dp思路。
状态定义：
定义dp[u][i]dp[u][i]dp[u][i]表示只考虑uuu子树外的点的情况下，dfs序中在uuu前面有iii个点的方案数。注意，这个dpdpdp值并不能直接作为答案，还要乘上uuu子树内部的所有可能的dfs序方案数。显然这个dpdpdp的取值与uuu子树的情况无关，因此这道题dpdpdp的转移与一般树形dpdpdp不同，这道题应当自上而下用父亲的信息更新儿子的信息。上文提到过，为了得到答案，我们还需要uuu子树内部的dfs序方案数量，因此定义dp2[u]dp2[u]dp2[u]表示uuu子树内的dfs序方案数。
状态转移：
设我们当前在uuu点，我们考虑更新uuu的一个儿子vvv的dpdpdp信息，我们需要知道dfs序有多少个点在vvv前面，我们把这些点分为在uuu的子树内和uuu的子树外两类，最后类似背包的思路合并即可。

• 对于uuu子树外的点的信息，我们通过uuu的dpdpdp值即可获得；
• 对于uuu子树内的点，在vvv前面的点的数量取决于uuu的儿子们的排列顺序，我们可以把u的所有儿子的子树大小sizsizsiz拿来做一次背包，与一般背包不同的是，后续用背包的结果更新dp值时还需要考虑放置顺序，因此我们还需要加一维表示当前背包的大小，便于考虑物品顺序。设c[i][j]c[i][j]c[i][j]表示放置了iii个物品，总大小为jjj的方案数，考虑放置子树vvv，则转移显然：c[i][j]=c′[i][j]+c′[i−1][j−siz[v]]c[i][j]=c'[i][j]+c'[i-1][j-siz[v]]c[i][j]=c′[i][j]+c′[i−1][j−siz[v]]
  c′c'c′表示未考虑vvv的dp值，ccc表示已考虑vvv的dp值，因此iii这一维倒序枚举更新即可不需要额外的数组。若我们要求vvv的dp值，则我们背包里需要删除vvv这个物品。由于背包dp的本质是一种多项式的卷积(此处的dp等价于c(y,x)=∏v∈sonu(1+y∗xsiz[v])c(y,x)=\prod_{v\in son_u}(1+y*x^{siz[v]})c(y,x)=∏v∈sonu​​(1+y∗xsiz[v]))，放置顺序无关紧要，我们不妨假设vvv是最后一个加入背包的物品。此时相当于我们已知c数组而需要求c′c'c′数组(注意，这里的c′c'c′数组在参考代码里就是ddd数组)。移项可得转移：
  c′[i][j]=c[i][j]−c′[i−1][j−siz[v]]c'[i][j]=c[i][j]-c'[i-1][j-siz[v]]c′[i][j]=c[i][j]−c′[i−1][j−siz[v]]
  在得到c′c'c′数组后，设在vvv前面有jjj个uuu子树内的点的方案数为b[j]b[j]b[j]，uuu一共有cntcntcnt个儿子，则有转移：
  b[j]=∑i=0cnt−1c′[i][j]∗i!∗(cnt−1−i)!b[j]=\sum_{i=0}^{cnt-1} c'[i][j]*i!*(cnt-1-i)!b[j]=i=0∑cnt−1​c′[i][j]∗i!∗(cnt−1−i)!
  而对于uuu这个点，它在dfs序中一定位于其他uuu子树内的点的前面，我们可以在设置ccc数组初值时考虑它，即:c[0][1]=1c[0][1]=1c[0][1]=1。
• 现在，我们已知bbb数组和dpdpdp数组，考虑用背包dp的思路对它们进行合并。但是我们目前仅考虑了u的儿子之间的排列顺序，尚未考虑这些儿子子树内的排序方案。设B=∏x∈sonudp2[x]B=\prod_{x\in son_u}dp2[x]B=∏x∈sonu​​dp2[x]。当我们用这些信息去更新vvv的dp值时，需要注意除去常数B中和vvv子树有关的信息。诚然，不除去这部分信息的话，我们直接得到的就是vvv的答案数组，但是这并不利于我们进一步dfs求v的子树的dp信息，因此我们在这里的处理是除去这部分信息。即定义C=∏x∈sonu,x≠v=Bdp2[v]C=\prod_{x\in son_u,x\neq v}=\frac B {dp2[v]}C=∏x∈sonu​,x​=v​=dp2[v]B​，有以下转移：
  对于i∈[1,n],dp[v][i]=C∗∑j=0siz[u]b[j]∗dp[u][i−j]对于i\in [1,n],dp[v][i]=C*\sum_{j=0}^{siz[u]}b[j]*dp[u][i-j]对于i∈[1,n],dp[v][i]=C∗j=0∑siz[u]​b[j]∗dp[u][i−j]
  （jjj的上确界是小于siz[u]siz[u]siz[u]的，比赛时为了求稳所以定枚举上界为siz[u]siz[u]siz[u]）

而对于dp2数组，我们需要在处理dp数组前就提前dfs一次先得到它。设uuu总共有cntcntcnt个儿子，考虑uuu子树内所有可能的dfs序，转移显然：
dp2[u]=cnt!∗∏dp2[v]dp2[u]=cnt!*\prod dp2[v]dp2[u]=cnt!∗∏dp2[v]
此时，第iii个点出现在dfs序中第jjj个位置的方案数就是dp[i][j−1]∗dp2[i]dp[i][j-1]*dp2[i]dp[i][j−1]∗dp2[i]。
参考代码：（比赛时写的代码）

#include
#define ll long long
using namespace std;
const int N=505,mod=998244353;
int n,dp[N][N],siz[N],c[N][N],d[N][N],b[N],fac[N],dp2[N];
vectorg[N];
void Add(int&x,int y){((x+=y)>=mod)&&(x-=mod);
}
inline int mul(int x,int y){return 1ll*x*y%mod;
}
inline int dec(int x,int y){return xint ret=1;while(b){if(b&1)ret=mul(ret,a);a=mul(a,a);b>>=1;}return ret;
}
void dfs1(int u,int fa){siz[u]=1;dp2[u]=1;int cnt=0;for(int v:g[u]){if(v==fa)continue;cnt++;dfs1(v,u);siz[u]+=siz[v];dp2[u]=mul(dp2[u],dp2[v]);}dp2[u]=mul(dp2[u],fac[cnt]);
}
void dfs2(int u,int fa){int cnt=0,sum=1;memset(c,0,sizeof c);c[0][1]=1;int lsr=1;for(int v:g[u]){if(v==fa)continue;cnt++;sum+=siz[v];lsr=mul(lsr,dp2[v]);for(int i=cnt;i>=1;i--)for(int j=sum;j>=siz[v];j--)Add(c[i][j],c[i-1][j-siz[v]]);}for(int v:g[u]){if(v==fa)continue;memset(d,0,sizeof d);for(int i=0;i<=cnt;i++)for(int j=0;j<=siz[u];j++)d[i][j]=dec(c[i][j],(j>=siz[v]&&i>0)?d[i-1][j-siz[v]]:0);memset(b,0,sizeof b);for(int i=0;iif(v!=fa)dfs2(v,u);}
}
int main()
{scanf("%d",&n);fac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);for(int i=2;i<=n;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dp[1][0]=1;dfs1(1,0);dfs2(1,0);for(int i=1;i<=n;i++){for(int j=0;j