大家好，我是ЭНТДЖЕЙ，今天是我2026年第十九次正式发题解！ 2026年发布的题解！ 能不能点个赞 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先简化题意： * 嗯对就是没什么好简化的 然后就是写代码: * 处理输入（READ）： * 正常输入 * 核心部分（PROCESS）： * 处理每个结点，如果他的子树中和以前有黑色结点，即在两个及以上个黑色结点中间的点，要将他变成黑色，但是这样处理，会出现本来就是黑色的结点，所以我新建了一个数组，来存储染色后是否为黑色 最后输出（WRITE）： * 输出结果 完整代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎉完结撒花🎉 想通了就会发现绿高了

@Author ylch 2025-12-14 疑似重题“[ABC368D] Minimum Steiner Tree” 思路1：任意两个黑点之间的所有白点都不能被删除，所以只需要把两个黑点之间的所有白点都变成黑点就可以。 为什么这样是正确的？因为这是一颗树，若两个黑点之间有一个白点，那么删掉它肯定是不行的，否则图会不连通。 所以我们只要以一个黑点为根，向下，若能到另外一个黑点，这期间的所有白点都会变成黑点。 思路2：发现最后留下的联通子图是唯一的，树上求子图，考虑树上dp 设dp[i]表示以i为根的子树中白点的数量 转移显然：dp[u]=(c[v]==0)+∑v∈son(u)dp[v]dp[u]=(c[v]==0)+\sum\limits_{v \in son(u)} dp[v]dp[u]=(c[v]==0)+v∈son(u)∑ dp[v] 答案显然即为dp数组中非0元素的个数 还有一个问题，所有白色结点的lca到根这一块dp数组是非0的，但这些结点并不包含在答案中 求lca再特判太麻烦，考虑做dp时以任意一个白点为根即可 思路3：考虑类似拓扑排序 最后合法的图一定是白色结点都位于最外部（类似于叶子）的位置，然后整个树的主干部分都是黑色 那么我们考虑用拓扑，每次把入度为0的白色结点删去并更新，直到无法删除，那么剩下的白点就都是要删的了