Shaking Trees
题外话
这题易哥哥跟我说这题的时候，点明了这题是关于高度\(100\)的\(O(n^3)\)或者\(O(n^4)\)的dp，还有提出切割点的概念使序列化。dp是真的，序列化也是真的。只能说易哥哥我的神。
不过其实切割点是根据树形态而变的，之前一直以为是不变的，歪了好久。不知道是我没get到易哥哥的真正思路还是啥。
题目
直接搬中文题面
解法
理论分析
首先最小操作数很显然就是树的高度。难点在于方案数。
如果不对树的根进行操作，可以认为那么树会被先分为两棵树，然后子树强制对根节点进行一次操作。那么子树强制对根节点进行一次操作这个是不会使方案更劣的，那么考虑树被为两棵树是否会导致操作数的增加。
- 方便起见，如果将\(u\)为根的子树分离不会使最小操作数变大，就称\(u\)为切割点。
假设原树高\(h\),我们把\(u\)为根的子树分离。\(u\)为根的子树高为\(h_u\),原树减去\(u\)为根的子树后，高为\(h'_u\)当且仅当\(h_u+h'_u=h\)才有操作数不增加。(操作数是不会变少的，\(h_u+h'_u<h\)是不可能的)
那么怎么样才会有\(h_u+h'_u=h\)呢？其实很简单，就是原树上深度大于\(h'_u\)的结点全部都在\(u\)的子树上。这样可以发现一个性质，就是原树上高度为\(h'_u+1\)对应\(u\)子树深度为\(1\)的点,也就是是子树的根\(u\)，也就是深度为\(h'_u\)的点只有一个\(u\)。
反过来也成立，如果没有和点\(u\)同深度的点，把\(u\)为根的子树分离不会增加最小操作数。
所以：没有和\(u\)同深度的结点\(\lrarr u\)是切割点。
再加上一个显然的性质：若没有和\(u\)同深度的结点，随便找一条从根节点到深度最大的叶节点之一的链，点\(u\)一定在上面。
所以我们可以把一棵树化为一个序列，方法就是找到一条上述的链，然后断链，原链上每一个点为根形成子树。记录子树的深度(只有一个点深度为\(0\))。深度序列根据链从根到叶排序。
由于性质，切割点一定都在链上。
然后问题是得到序列怎么判定切割点，即判断某个点的深度上是否只有一个点。
记序列为\(d\),若链(序列)上第\(i\)个点为切割点，则满足
\(\forall j\in[1,i-1],d_j+j<i\)
例如序列为\(1,1,0\)那么链上第\(2,3\)个点都不是切割点。序列\(1,0,0\),第三个点为切割点。(序列第一个点，也就是根，肯定是切割点，就不说了)
- 序列尾一定是\(0\)
DP
这样理论就铺垫完成了。接下来上DP
首先一个序列有对应有一个方案数。
核心逻辑是分离树的时候会把大序列分为两个小序列，这样用区间DP就可以。
记\(dp_{L,R,A}\)为序列\(d(A)[L:R]\)的方案数。序列\(d(A)\)由\(d,A\)确定，\(d(A)_i=max(d_i-A,0)\)
序列\(d(A)[L:R]\)对下标\(k(L<k<R)\)进行一次操作,序列一分为二，所有\(k\)及之后的子树深度会减\(1\)序列上的\(R\)被删去,原序列会变成这样两个序列\(d(A)[L:k-1],d(A+1)[k:R-1]\)
记\(Cut\)为对应序列切割点下标集合(不包括根和叶),\(C(m,n)\)为组合数,我习惯\((m\ge n)\)
转移方程$$dp_{L,R,A}=dp_{L,R-1,A}+dp_{L,R-1,A+1}+\sum_{k\in Cut} dp_{L,k-1,A}\times dp_{k,R-1,A+1} \times C(R-L.k-L)$$
\(L=R\)特判即可。
\(Cut\)遍历时顺便求就可以。
出现组合数是因为被分为了两颗树，两棵树独立，操作顺序随意取，余下\(R-L\)次操作里取\(k-L\)次给前面一棵树，其余给后面一棵树就有了一个组合数。
复杂度
- \(h\)指代高度
\(O(h^3)\)状态,\(O(h)\)转移，\(O(h^4)DP,O(n)dfs\)总复杂度\(O(h^4+n)\)
代码
点我查看代码
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
typedef int LL;
inline LL Read(){
LL x=0;char ch=getchar();bool f=0;
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);
if(f) x=-x;return x;
}
const signed maxn=2e5+5,mod=1e9+7,S=105,MX=100;
int add(int a,int b){
return ((a+=b)>=mod)?a-mod:a;
}
int mul(int x,int y){
return (ll)x*y%mod;
}
int fpow(int a,int b){
int ans=1;
while(b){
if(b&1) ans=mul(ans,a);
a=mul(a,a);b>>=1;
}
return ans;
}
std::vector<int> g[maxn];
int dep[maxn],maxd,md[maxn],sd[maxn],fa[maxn];
int dp[S][S][S],mx[S][S];//dp[L][R][effictive operation count in[1,L]]
int cnt,len[S],jc[MX+5],inv[MX+5];
void dfs(int u,int Fa){
fa[u]=Fa;dep[u]=dep[Fa]+1;
if(dep[u]>dep[maxd]) maxd=u;
for(auto v:g[u]){
if(v==Fa) continue;
dfs(v,u);
int dv=md[v]+1;
if(dv>md[u]) std::swap(dv,md[u]);
if(dv>sd[u]) std::swap(dv,sd[u]);
}
}
int C(int m,int n){
if(m<0||n<0||m<n) return 0;
return mul(jc[m],mul(inv[n],inv[m-n]));
}
signed main(){
jc[0]=inv[0]=1;
for(int i=1;i<=MX;++i) jc[i]=mul(jc[i-1],i);
inv[MX]=fpow(jc[MX],mod-2);
for(int i=MX-1;i;--i) inv[i]=mul(inv[i+1],i+1);
int n=Read();
for(int i=1;i<n;++i){
int u(Read()),v(Read());
g[u].push_back(v);g[v].push_back(u);
}
dfs(1,0);
cnt=dep[maxd];
for(int i=1;i<=cnt;++i){
//printf("%d%c",maxd," \n"[i==cnt]);
len[cnt-i+1]=sd[maxd];
maxd=fa[maxd];
}
for(int i=1;i<=cnt;++i){
mx[i][i]=len[i];
for(int j=0;j<len[i];++j) dp[i][i][j]=0;
for(int j=len[i];j<=cnt;++j) dp[i][i][j]=1;
}
for(int lenth=1;lenth<cnt;++lenth){
for(int L=1;L+lenth<=cnt;++L){
int R=L+lenth;
mx[L][R]=std::max(mx[L][R-1],mx[L+1][R]);
for(int j=0;j<mx[L][R];++j){
dp[L][R][j]=0;
if(len[R]>j) continue;
dp[L][R][j]=add(dp[L][R-1][j+1],dp[L][R-1][j]);//do operation on L,R
int link=std::max(L,L+len[L]-j);
for(int k=L+1;k<R;++k){
if(k>link){
dp[L][R][j]=add(dp[L][R][j],mul(C(R-L,k-L),mul(dp[L][k-1][j],dp[k][R-1][j+1])));
link=std::max(k,k+len[k]-j);
}
else link=std::max(link,k+len[k]-j);
}
}
for(int j=mx[L][R];j<=cnt;++j) dp[L][R][j]=jc[R-L+1];
}
}
//for(int i=1;i<=n;++i) printf("<%d,%d,%d>%c",i,md[i],sd[i]," \n"[i==n]);
//for(int i=1;i<=cnt;++i) printf("%d%c",len[i]," \n"[i==cnt]);
/*
for(int j=0;j<=cnt;++j){
for(int L=1;L<=cnt;++L){
for(int R=L;R<=cnt;++R){
printf("%d%c",dp[L][R][j]," \n"[R==cnt]);
}
}putchar('\n');
}
//*/
printf("%d %d\n",cnt,dp[1][cnt][0]);
return 0;
}