我们先不考虑边的权值(< 与>)，这样子 $n-1$ 条边组成的就是树了，很显然是需要我们求出这棵树的合法拓扑序的个数，考虑使用 $\rm{DP}$ ，对于边的方向(即<,>) ，我们分类讨论即可。
首先的一个想法就是设 $f_u$ 表示点 $u$ 的子树的合法拓扑序的总数，但是这个时候如何计算呢，对于一个 $u$ 的儿子 $v$ ，我们虽然知道 $u$ 和 $v$ 的攻克的前后关系，但是合并答案貌似并不好合并。这个时候我们增加一维 $j$ ，$f_{u,j}$ 表示 $u$ 的子树的所有合法拓扑序中 $u$ 在第 $j$ 位上的总状态数。
也就是说，对于一个必须在 $u$ 前面攻克的关卡 $v$ ，我们考虑枚举一个 $j$ ，$v$ 子树中 $j$ 个结点在合并 $u,v$ 后放到 $u$ 前面，另外 $sz_v-j$ 个放到 $u$ 后面，然后枚举一个 $k$ ，表示当前的 $v$ 排在 $v$ 子树的拓扑序中的第 $k$ 位，只有 $k\leq j$ 的时候 $v$ 才可以转移 $u$ ，因为这个时候 $v$ 在 $u$ 前面。
现在再来考虑 $“$ $j$ 个结点放在 $u$ 前面 $”$ 的方案数和 $“$ $sz_v-j$ 个结点放在 $u$ 后面的方案数 $”$，这个显然可以用组合数算，合并 $v$ 的子树后，$u$ 的排名从 $i$ 变成了 $i+j$ ，也就是说我们需要将 $j$ 个乱序插入到 $u$ 前面 $i+j-1$ 个数中，方案数显然为 $C_{i+j-1}^{j}$ ，那么现在总节点数显然为 $sz_u+sz_v$ (现在 $sz_u$ 和 $sz_v$ 还没有并在一起) ，$u$ 后面理所当然有 $sz_u+sz_v-i-j$ 个位置，将 $sz_v-j$ 个数插进去的方案数显然为 $C_{sz_u+sz_v-i-j}^{sz_v-j}$ 个，这两个数再乘上 $f_{u,i}$ 和 $f_{v,k}$ 就好了，这一次合并后 $u$ 的位置显然到了 $i+j$ ，所以 $f_{u,i+j}$ 显然要加上这一组贡献。
经整理后的转移方程如下：
$$pls(f_{u,i+j},f_{u,i}\cdot f_{v,k}\cdot C_{i+j-1}^{j}\cdot C_{sz_u+sz_v-i-j}^{sz_v-j})$$
代码就是这样写：
for i=1 to sz[u]
for j=1 to sz[v]
for k=1 to j
pls(f[u][i+j],f[u][i]*f[v][k]*C[i+j-1][j]*C[sz[u]+sz[v]-i-j][sz[v]-j])
这是 $n^3$ 的，过不去。考虑前缀和优化，几下 $f_v$ 的前缀和，最后的一层循环就可以直接丢掉了。
这个就是 $v$ 要在 $u$ 前面的情况，$u$ 在 $v$ 前面的情况和这个差不多，不过转移的时候 $j$ 就要从 $0$ 开始了，因为那个时候 $u$ 前面是可以不多放任何东西的，还有就是 $u$ 在 $v$ 前面的时候注意 $k\geq j$ 时才可以转移 !
最后的答案就是 $\sum\limits_{i=1}^{n} f_{1,i}$ 啦。
Code:
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e3+9;
const int mod=1e9+7;
int head[N],cnt;
struct Edge{int nxt,to,val;}G[N<<1];
int C[N][N],f[N][N],pre[N][N],suf[N][N],sz[N],g[N];
void add(int u,int v,int w) {
G[++cnt]=(Edge){head[u],v,w},head[u]=cnt;
G[++cnt]=(Edge){head[v],u,w^1},head[v]=cnt;
}
namespace OI {
void pls(int&x,int y) {x+=y;if(x>=mod)x-=mod;}
template <typename _Tp> inline void IN(_Tp&x) {
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;
}
}using namespace OI;
void dfs(int u,int fa) {
sz[u]=f[u][1]=1;
for(int l=head[u];l;l=G[l].nxt) {
int v=G[l].to,w=G[l].val;
if(v==fa) continue;
dfs(v,u);
memset(g,0,sizeof(g));
if(w) {
for(int i=1;i<=sz[u];++i)
for(int j=1;j<=sz[v];++j)
pls(g[i+j],1ll*f[u][i]*pre[v][j]%mod*C[i+j-1][j]%mod
*C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
} else {
for(int i=1;i<=sz[u];++i)
for(int j=0;j<=sz[v];++j)
pls(g[i+j],1ll*f[u][i]*suf[v][j+1]%mod*C[i+j-1][j]%mod
*C[sz[u]+sz[v]-i-j][sz[v]-j]%mod);
}
sz[u]+=sz[v];
memcpy(f[u],g,sizeof(g));
}
pre[u][0]=suf[u][sz[u]+1]=0;
for(int i=1;i<=sz[u];++i) pre[u][i]=(pre[u][i-1]+f[u][i])%mod;
for(int i=sz[u];i>=1;--i) suf[u][i]=(suf[u][i+1]+f[u][i])%mod;
}
int solve() {
memset(head,0,sizeof(head)),cnt=0;
memset(f,0,sizeof(f));
int n;IN(n);
for(int i=1;i<n;++i) {
int u,v;char sign;
IN(u),sign=getchar(),IN(v);
add(u+1,v+1,sign=='<'?0:1);
}
dfs(1,0);
int ans=0;
for(int i=1;i<=n;++i) pls(ans,f[1][i]);
return ans;
}
int main() {
/*预处理组合数*/
for(int i=0;i<=N-2;++i) C[i][0]=1;
for(int i=1;i<=N-2;++i)
for(int j=1;j<=N-2;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
int T;IN(T);
while(T--) printf("%d\n",solve());
return 0;
}
可能有人会问，如果 $u$ 的儿子 $v$ 下面的边全都是 $>$ ，并且 $u$ 连向 $v$ 的边也是 $>$ ，那么这个时候 $v$ 以及其子树的所有点都必须在 $u$ 前面完成，在转移的时候为什么可以 $“$ 提出 $j$ 个结点放到 $u$ 后面 $”$ 呢？
其实想想就可以明白，在向上统计答案的时候对于一个 $v$ 的儿子 $a$ ，我们只统计了合并后 $a$ 在 $v$ 前面的情况，同样在 $u$ 统计 $v$ 时也只是统计了合并后 $v$ 在 $u$ 前面的情况，所有我们也只是统计了 $“$ $a$ 在 $v$ 前面且 $v$ 在 $u$ 前面 $”$ 的情况，所有被统计的情况一定是合法的。
0 条评论