前者是后者各方面的强化版。
容易想到设f[i][j]表示i子树中第j小的是i的方案数（即只考虑相对关系）。比较麻烦的在于转移。考虑逐个合并子树。容易想到枚举根原来的排名和子树根原来的排名，算一发组合数。具体要考虑的是当前有n个0、m个1，将他们排成一排，要求其中第x个0在k号位，第y个1在k号位的右边（1表示要合并上去的子树中的节点，对应父亲<儿子的情况）。那么显然当y>k-x时存在方案，且方案数为C(k-1,x-1)·C(n+m-k,n-x)。父亲>儿子的情况类似。直接算就是O(n3)的，前缀和优化一发就可以做到O(n2)了，因为这种类似背包的与子树大小相关的转移相当于在LCA处考虑每个点对。
upd：突然发现之前写的复杂度是假的……改正确了一点莫名其妙拿了luogu rank1。
#include#include #include #include #include #include using namespace std;#define ll long long#define N 1010#define P 1000000007char getc(){ char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c!='<')&&(c!='>')) c=getchar();return c;}int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}int T,n,f[N][N],C[N][N],size[N],p[N],t;struct data{ int to,nxt,op;}edge[N<<1];void addedge(int x,int y,int op){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].op=op,p[x]=t;}void inc(int &x,int y){x+=y;if (x>=P) x-=P;}inline int c(int n,int m){ return C[n][m];}void dfs(int k,int from){ size[k]=1;memset(f[k],0,sizeof(f[k]));f[k][1]=1; for (int i=p[k];i;i=edge[i].nxt) if (edge[i].to!=from) { dfs(edge[i].to,k); for (int j=size[k]+size[edge[i].to];j>=1;j--) { int s=0; for (int x=max(1,j-size[edge[i].to]);x<=min(j,size[k]);x++) if (edge[i].op) inc(s,1ll*f[k][x]*c(j-1,x-1)%P*c(size[k]+size[edge[i].to]-j,size[k]-x)%P*f[edge[i].to][j-x]%P); else inc(s,1ll*f[k][x]*c(j-1,x-1)%P*c(size[k]+size[edge[i].to]-j,size[k]-x)%P*(f[edge[i].to][size[edge[i].to]]-f[edge[i].to][j-x]+P)%P); f[k][j]=s; } size[k]+=size[edge[i].to]; } for (int i=1;i<=size[k];i++) inc(f[k][i],f[k][i-1]);}int main(){#ifndef ONLINE_JUDGE freopen("bzoj3167.in","r",stdin); freopen("bzoj3167.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif T=read(); while (T--) { n=read(); memset(p,0,sizeof(p));t=0; for (int i=1;i