@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的白色结点删去并更新，直到无法删除，那么剩下的白点就都是要删的了