题解 CF735E 【Ostap and Tree】

· · 题解

思路来自@skylee，但他呀讲得不太对的亚子。

不关心 是怎么想到的 的话可跳转至Part2的DP部分。

Part 1

树形DP。定义着色点为着色点，合法点为与最近的着色点距离不超过 k 的点，合法子树为全由合法点构成的子树。

考虑要加上哪些状态。DP合并时，子树与子树之间有哪些相互作用呢？无非是一棵子树 A 中的着色点对子树 B 中的某些非合法点产生了贡献（使之变成合法点）。

所以我们设 f_{x,i,j} 表示以 x 为根的子树，子树内离 x 最近的着色点到 x 的距离为 i，子树内离 x 最远的非合法点到 x 的距离为 j。然后就可以转移了。时间复杂度 \Theta(nk^4)，看一下数据范围好像能过？这就是 k 搞这么小的意义所在吗。

Part 2

我们不满足于这个不优美的做法，考虑对其进行优化。

有一个性质： 两棵非合法子树合并后，最深的非合法点不可能被消去 。

证明：
假设我们要合并 f_{x,i,j} 与 f_{y,i',j'}
其中 i,i',j,j'<k，j\ge j'+1


因为 x2,y2不合法，所以 i+j>k,i'+j'>k
如果合并后 x2 变成了合法点，则 i'+1+j\le k，又 j'+1\le j 所以 i'+1+j'+1\le k，与 i'+j'>k 矛盾。

这个性质告诉我们，对于非合法子树，j 的转移与 i 无关，可以扬弃 i 这维状态。

定义新的DP状态 f_{x,i},0\le i \le 2k
当 0\le i \le k 时，表示以 x 为根的子树是一棵合法子树，且子树内离 x 最近的染色点与 x 的距离为 i；
当 k+1\le i \le 2k 时，表示以 x 为根的子树是一棵非合法子树，且子树内离 x 最远的非合法点与 x 的距离为 i-k-1。

答案为 \sum_{0\le i \le k} f_{1,i} 。
一个孤点的DP值为 f_{x,0}=f_{x,k+1}=1
考虑如何合并 f_{x,i} 与 f_{y,j}

  1. 当 i\le k,j\le k 时，合并为 f_{x,min(i,j+1)}；
  2. 当 i\le k,j> k,i+j-k\le k 时，x 内的染色点可以贡献到 y 内的非合法点，所以合并为 f_{x,i}；
  3. 当 i\le k,j> k,i+j-k> k 时，合并为 f_{x,j+1}；
  4. 当 i> k,j> k 时，合并为 f_{x,max(i,j+1)}；

于是就得到了代码中神奇的一句话转移：
t[i+j<=2*k?min(i,j+1):max(i,j+1)]+=f[x][i]*f[y][j]

时间复杂度 \Theta(nk^2)。

Comment：Part1 大概是 2500 的亚子，Part2 可能有 3000？最扯的是这个 2500 的DP都可以黑啊。 

#include<bits/stdc++.h> 
#define mk make_pair
#define pk push_back 
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;
template<class T> bool cmax(T &x,T y){return y>x?x=y,1:0;}
template<class T> bool cmin(T &x,T y){return y<x?x=y,1:0;}
const int N=105,K=45,mod=1e9+7;
int n,k,f[N][K],t[K];
vector<int> to[N]; 
void dfs(int x,int pre){
    f[x][0]=1,f[x][k+1]=1;
    for(auto y:to[x])if(y^pre){
        dfs(y,x);
        memset(t,0,sizeof t);
        for(int i=0;i<=2*k;++i)
            for(int j=0;j<=2*k;++j)
                (t[i+j<=2*k?min(i,j+1):max(i,j+1)]+=1ll*f[x][i]*f[y][j]%mod)%=mod;
        memcpy(f[x],t,sizeof t);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1,x,y;i<n;++i) cin>>x>>y,to[x].pk(y),to[y].pk(x);
    dfs(1,0); 
    int ans=0;
    for(int i=0;i<=k;++i) (ans+=f[1][i])%=mod;
    cout<<ans<<endl;
    return 0;
}