洛谷 4099 [HEOI2013]SAO——树形DP

题目：https://www.luogu.org/problemnew/show/P4099

结果还是看了题解才会……

关键是状态，f[ i ][ j ] 表示 i 子树、 i 号点是第 j 个出现的方案数。

合并的时候，很重要的是去枚举孩子 v 有 k 个点放在了第 i 个点前面。这样 v 可以在的位置就根据该边是 > 还是 < 而是一个前/后缀。这样就是 n 的了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

const int N=,mod=1e9+;

int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}

int n,siz[N],c[N][N],f[N][N],pr[N][N],sc[N][N];

int hd[N],xnt,to[N<<],nxt[N<<];bool lx[N<<];//1:<

char ch;

void add(int x,int y,bool fx)

{ to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;lx[xnt]=fx;}

void dfs(int cr,int fa)

{

  siz[cr]=; f[cr][]=;//

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    dfs(v,cr); siz[cr]+=siz[v];

    for(int j=siz[cr];j;j--)

      {

        int lj=;

        for(int k=,l2=Mn(j-,siz[v]);k<=l2;k++)

          {

        int tp=;

        if(lx[i]) tp=(ll)f[cr][j-k]*sc[v][k+]%mod;

        else tp=(ll)f[cr][j-k]*pr[v][k]%mod;

        tp=(ll)tp*c[j-][k]%mod*c[siz[cr]-j][siz[v]-k]%mod;

        lj=upt(lj+tp);

          }

        f[cr][j]=lj;

      }

      }

  pr[cr][]=sc[cr][siz[cr]+]=;///

  for(int j=;j<=siz[cr];j++)

    {

      pr[cr][j]=upt(pr[cr][j-]+f[cr][j]);

    }

  for(int j=siz[cr];j;j--)

    {

      sc[cr][j]=upt(sc[cr][j+]+f[cr][j]);

    }

  pr[cr][]=sc[cr][siz[cr]+]=;

}

int main()

{

  int T=rdn(),lm=;

  for(int i=;i<=lm;i++)c[i][]=;

  for(int i=;i<=lm;i++)

    for(int j=;j<=i;j++)

      c[i][j]=upt(c[i-][j]+c[i-][j-]);

  while(T--)

    {

      n=rdn(); memset(hd,,sizeof hd); xnt=;

      for(int i=,u,v;i<n;i++)

    {

      u=rdn()+;cin>>ch;v=rdn()+;

      add(u,v,ch=='<'); add(v,u,ch=='>');

    }

      dfs(,);

      printf("%d\n",sc[][]);

    }

  return ;

}