P11529
Solution
题意已经给的很清楚了，稍微推一下就可以发现这题是一个树上动态规划，考虑状态 $f_{i,j}$ 表示在第 $i$ 个节点状态为 $j$ 的情况下子树内需要染白的个数，因为只要染一定数量的白色，那么黑色的数量就可以被限制住，也就是不能改变其他的点变成黑色。
考虑状态，灰色的点有三种情况：
-
不会被黑色染，也就是不用白色相邻，$j=0$。
-
需要白色的保护，是否与白色相邻，$j=1/2$。
而如果是白色或者黑色的，就不需要讨论，$j=3/4$。
现在考虑转移，最好想的是黑色的点，只用考虑 $f_{i,4}=\sum \min(f_{j,1},f_{j,3},f_{j,4})$，因为可以是不用或者已经与白色相邻的灰点，白点，或者黑点。
然后就是白点，不用管，$f_{i,3}=1$，因为子树是不会被影响到的，即黑色无法向下传递。
灰点我们在定义的时候考虑了白点，但是我们还要考虑与黑色相邻的情况。
与黑点相邻时，必须与白点相邻，所以 $f_{i,0/4}$ 不用考虑。然后就是 $f_{i,0}$ 这个地方我原来用了一种复杂的方法实现，后来在题解中找到了一个简单的做法，如下：
for(auto i : g[x]){//遍历儿子
if(i!=fa){
LL mn=min(f[i][0],min(f[i][1],min(f[i][3],f[i][4])));//找到所有情况里最小的
f[x][1]+=mn;//加上去
if(!vis[i]){//如果是黑点
tmp=min(tmp,f[i][3]-mn);//最小的一个差
}
}
}
f[x][1]+=tmp;//补上那么这样的原理是有一个儿子我们必须要选到 $f_{j,3}$ 但是不知道是哪一个，就先加上 $mn$，然后记录一下最小的 $f_{j,3}-mn$，最后把这个最小的再补上去，就是最小的答案。
然后是 $f_{i,2}=\sum \min(f_{i,0},f_{i,1},f_{i,4})$，不选 $f_{i,3}$ 是因为本来定义就不能和白点相邻，$f_{i,2}$ 是因为已经和黑点相邻了，不能不和白点相邻。$f_{i,3}$ 就是所有最小值的和，因为自己就是白点，不用考虑儿子的颜色。
现在如果这个点是灰色且不与黑色相邻，那么它也不需要与白色相邻，所以 $f_{i,0}=\sum \min(f_{j,0},f_{j,1},f_{j,3})$，不与黑色相邻就不需要考虑儿子是黑点，儿子是灰点也不需要与白色相邻。如果本来就是白点，那么 $f_{i,3}=\sum \min(f_{j,0},f_{i,2},f_{j,1},f_{j,3})$，只需要满足不与黑色相邻的条件就好了。
答案即为根的最小值。
以上难免有思维不严谨的地方，见谅。
Code
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
const LL inf=1e12;
LL n,k,f[1000005][5];
vector<LL> g[1000005];
bool vis[1000005],flag[1000005];
void dfs(LL x,LL fa){
f[x][3]=1;
for(auto i : g[x]){
if(i!=fa) dfs(i,x);
}
if(vis[x]){
f[x][0]=f[x][1]=f[x][2]=f[x][3]=inf;
for(auto i : g[x]){
if(i!=fa) f[x][4]+=min(f[i][1],min(f[i][3],f[i][4]));
}
}else if(flag[x]){
f[x][0]=f[x][4]=inf;
LL tmp=inf;
for(auto i : g[x]){
if(i!=fa){
f[x][2]+=min(f[i][0],min(f[i][1],f[i][4]));
f[x][3]+=min({f[i][0],min(f[i][1],f[i][4]),min(f[i][2],f[i][3])});
LL mn=min(f[i][0],min(f[i][1],min(f[i][3],f[i][4])));
f[x][1]+=mn;
if(!vis[i]){
tmp=min(tmp,f[i][3]-mn);
}
}
}
f[x][1]+=tmp;
}else{
f[x][1]=f[x][2]=f[x][4]=inf;
for(auto i : g[x]){
if(i!=fa){
f[x][0]+=min(f[i][0],min(f[i][1],f[i][3]));
f[x][3]+=min(f[i][0],min(f[i][1],min(f[i][3],f[i][2])));
}
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=1,x;i<=k;i++){
cin>>x;vis[x]=1;
}
for(int u,v,i=1;i<n;i++){
cin>>u>>v;
g[u].push_back(v);g[v].push_back(u);
flag[u]|=vis[v];flag[v]|=vis[u];
}
dfs(1,0);
cout<<min(f[1][0],min(f[1][1],min(f[1][3],f[1][4])));
return 0;
}