题解：P12734 理解
VinstaG173
·
·
题解
题意转化
形式化题意：给定有根森林，点有点权，边有边权。一个子图的权值为其中每棵树根结点的点权加所有边的边权，求一个权值最小的，包含所有给定的关键点的子图（显然子图为一个森林），使得其中所有树都 k-合法。
其中一棵树 k-合法的定义是存在一种遍历整棵树的方式，维护一个集合，初始为根结点单点集，每次可以从中删除任意元素或加入其中任意元素的一个儿子，使得所有结点均加入过集合一次，且任意时刻集合的大小不超过 k。
下文中用选择/不选择结点 u 表示 u 在/不在子图中。
Subtask 1
注意特判 $k=1$，此时必须选单点。以下只考虑 $k\ge2$。
### Subtask 2
链部分分。容易发现我们可以在链上不断地加入儿子后直接删除父亲，显然只要 $k\ge2$ 就可以遍历任意长的链。那么问题就变成简单地求权值最小的子图。
考虑选择了哪些点。首先子树里没有关键点的可以整个丢掉。记 $f_{u,1/0}$ 表示包含 $u$ 的子树内所有关键点，且 $u$ 有/没有被选择时的最小权值，其中 $f_{u,1}$ 不包含 $r_u$ 的点权或 $t_u$ 的边权。则对于非叶子结点可以列出转移方程：
$$f_{u,0}=\min(f_{u+1,0},f_{u+1,1}+r_{u+1}),\\
f_{u,1}=\min(f_{u+1,0},f_{u+1,1}+\min(r_{u+1},t_{u+1})).$$
特别地，当 $u=x_i$ 时 $f_{u,0}$ 应为 $+\infty$。以下同样不再赘述。
### Subtask 4
菊花图部分分。容易发现可以在菊花图上不断加入儿子后直接删除儿子，同样只要 $k\ge2$ 就能遍历任意菊花图。
同上列出状态 dp，其中 $ch(u)$ 表示 $u$ 的子结点集合：
$$f_{u,0}=\sum_{v\in ch(u)}\min(f_{v,0},f_{v,1}+r_v),\\
f_{u,1}=\sum_{v\in ch(u)}\min(f_{v,0},f_{v,1}+\min(r_v,t_v)).$$
注意到上述转移方程的性质，若视为存在点 $0$，则答案即为 $f_{0,0}$。
### Subtask 3
实际解法上只有实现上的方便（只有两个儿子）。
通过手玩满二叉树或许能够发现关于一棵树最少需要多大的 $k$ 才能合法的性质。直接讲正解。
### Subtask 5
对每棵求出的树直接模拟验证合法的过程显然复杂度太高，因此我们考虑刻画合法的树的性质。
通过链的部分分我们发现如果只剩一个儿子，那么可以直接删除父亲往前遍历。
如果根结点有一个子结点的子树 $k$-合法，且其他子结点的子树均 $(k-1)$-合法，则可以保留根结点，依次遍历所有 $(k-1)$-合法的子树，最后删除根遍历 $k$-合法的子树，从而全树也是 $k$-合法的。
如果根结点有至少两棵子树不是 $(k-1)$-合法的，设为 $T_1,T_2$，若原树是 $k$-合法的，则在任意一个合法的遍历过程中，不妨设 $T_2$ 比 $T_1$ 更晚遍历完。为了遍历 $T_2$，在遍历 $T_1$ 的过程中必须保留一个不在 $T_1$ 中的结点，这个过程中一定会有一个时刻集合中点数超过 $k$，与原树 $k$-合法矛盾。
因此一棵树 $k$-合法当且仅当它的根结点的至多一个子结点的子树 $k$-合法，且其他子结点的子树都 $(k-1)$-合法。
那么我们可以设出状态：$f_{u,i}$ 表示子图中 $u$ 为根的子树 $i$-合法时的最小权值。在原图中 $u$ 的子树内可能还有其他树，它们只要是 $k$-合法的即可。特别地，$f_{u,0}$ 表示 $u$ 不选时的最小权值。
则首先有转移：
$$f_{u,0}=\sum_{v\in ch(u)}\min(f_{v,0},f_{v,k}+r_v).$$
若选择 $u$，对于 $f_{u,1}$，由于不能用 $t_v$ 转移，因此转移式跟 $f_{u,0}$ 是一样的。
当 $i\ge2$，对于 $v\in ch(u)$，有三种转移情形：$v$ 不选，此时用于转移的是 $f_{v,0}$；$v$ 作为子图中树的根，此时用于转移的是 $f_{v,k}+r_v$；$v$ 作为子图中 $u$ 的儿子，此时用于转移的是 $f_{v,i-1}+t_v$，或有一个 $v$ 是 $f_{v,i}+t_v$。
因此若前三项中有最小值，则直接用于转移；否则对剩余的 $v$，最小值为 $f_{v,i}+t_v$，选择一个 $f_{v,i}+t_v-\min(f_{v,0},f_{v,k}+r_v,f_{v,i-1}+t_v)$ 最小的取 $f_{v,i}+t_v$，其余的取前三者的最小值转移。在实现上可以直接对前三者取 $\min$ 后求和，然后对差值与 $0$ 取 $\min$ 后加入转移答案即可。
时间与空间复杂度均为 $O(nk)$。
Code:
```cpp
int n,m,k;
ll r[100003];
ll t[100003];
int d[100003];
int tg[100003];
ll f[100003][13];
ll mind[100003][13];
vector<int>e[100003];
inline void solve(){
cin>>n>>m>>k;
for(int i=0;i<=n;++i){
d[i]=tg[i]=0;e[i].clear();
for(int j=0;j<=k;++j)
f[i][j]=mind[i][j]=0;
}for(int i=1,p;i<=n;++i){
cin>>p;++d[p];
e[p].push_back(i);
}for(int i=1;i<=n;++i)cin>>r[i];
for(int i=1;i<=n;++i)cin>>t[i];
for(int i=1,x;i<=m;++i){
cin>>x;tg[x]=1;f[x][0]=1e16;
}for(int u=n;u;--u){
if(!d[u])continue;
for(int i=0,v;i<d[u];++i){
v=e[u][i];ll f1,f2;
for(int j=2;j<=k;++j){
f1=min(f[v][0],min(f[v][k]+r[v],f[v][j-1]+t[v]));
f2=f[v][j]+t[v];f[u][j]+=f1;
mind[u][j]=min(mind[u][j],f2-f1);
}f[u][1]+=min(f[v][0],f[v][k]+r[v]);
}for(int j=2;j<=k;++j){
f[u][j]+=mind[u][j];
f[u][j]=min(f[u][j],f[u][j-1]);
}if(!tg[u])f[u][0]=f[u][1];
}for(int i=0,v;i<d[0];++i)
v=e[0][i],f[0][0]+=min(f[v][0],f[v][k]+r[v]);
cout<<f[0][0]<<"\n";
}
```