自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 23:17:48，当前版本为作者最后更新于2025-06-07 20:43:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意转化

形式化题意：给定有根森林，点有点权，边有边权。一个子图的权值为其中每棵树根结点的点权加所有边的边权，求一个权值最小的，包含所有给定的关键点的子图（显然子图为一个森林），使得其中所有树都 $k-$合法。

其中一棵树 $k-$合法的定义是存在一种遍历整棵树的方式，维护一个集合，初始为根结点单点集，每次可以从中删除任意元素或加入其中任意元素的一个儿子，使得所有结点均加入过集合一次，且任意时刻集合的大小不超过 $k$。

下文中用选择/不选择结点 $u$ 表示 $u$ 在/不在子图中。

Subtask 1

$O(2^n)$ 枚举子图中的点，再 $O(n)$ 验证树的合法性及计算权值，总之随便暴力可过。

注意特判 $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:

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";
}