题解 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都可以黑啊。 ```cpp #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; } ```