题意
给定 \(n,d\)，A 和 B 玩游戏：A 指定一棵度数不超过 \(d\) 的、\(n\) 个点的带标号无根树 \(T\)；接着 B 指定两个节点 \(u,v(u\neq v)\) 将 \(u\) 到 \(v\) 路径上的点编号取出作为序列 \(a[1..m]\)；接着 A 指定 \(1\leq k< m,\mathit{op}\in\{0,1\}\)，进行以下操作：
- 若 \(\mathit{op}=0\)，取出 \(a[k+1..m]\)，翻转，并加上 \(a[k]\)，放回原位；
- 若 \(\mathit{op}=1\)，取出 \(a[k+1..m]\)，取负，并加上 \(a[k]\)，放回原位。
最后若序列 \(a\) 单调，A 获胜。问若双方都采用最优策略，有多少可能的五元组 \((T,u,v,k,\mathit{op})\)。对给定模数取模。\(n\leq 200\)
题解
若序列 \(a\) 在最后一步之前单峰，则 A 有必胜策略，且恰好有四种。于是我们只需要统计所有路径都单峰的树的数量。这样的树一定可以找到一些结点满足所有点到它的路径都是单调的，这些结点构成一个连通块从而可以点减边。考虑计算 \(i\) 个点、根度数为 \(j\) 的这样的树的数量，可以 DP。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=210;
int n,d,mod;
ll c[N][N],f[N][N],g[N];
int main(){
cin>>n>>d>>mod;
f[1][0]=1;
g[1]=1;
for(int i=c[0][0]=1;i<=n;i++)
for(int j=c[i][0];j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
for(int i=2;i<=n;i++){
ll w=0;
for(int j=1;j<=i&&j<=d;j++){
ll t=0;
for(int k=1;k<i;k++)
t=(t+f[i-k][j-1]*1ll*g[k]%mod*c[i-2][k-1])%mod;
f[i][j]=t;
if(j<d)
w=(w+t)%mod;
}
g[i]=w;
}
ll ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<=d;j++)
if(j!=1)
for(int k=0;j+k<=d;k++)
ans=(ans+f[i+1][j]*1ll*f[n-i][k])%mod;
ans<0&&(ans+=mod);
ans=ans*2ll*n*(n-1)%mod;
cout<<ans<<endl;
}