lgswdn_SA
2020-05-08 13:06:12
由于一旦 B 进入了一个子树,那么他就不会出来(因为不会免费赠送 A 一个涂色的机会)。所以这个问题仍然适用和子树相关的树形
我们对
对于一个节点
所以我们可以设立状态,表示这个节点需要自己的祖先提前染色多少节点才能覆盖住整个子树。
最终要求根节点为
对于转移,一个节点需要的,即给自己的儿子节点染色所需要的和来自自己儿子子树的求助。因为儿子没法帮助祖先,所以如果发现自己还有很多空余的染色机会没用或者正好用完,那么
要注意
#include<bits/stdc++.h>
using namespace std;
const int N=300009;
vector<int>e[N];
int f[N];
int dp(int u,int fa,int k) {
for(int i=0,v;i<e[u].size();i++)
if((v=e[u][i])!=fa) {
dp(v,u,k);
f[u]+=(1+f[v]);
}
f[u]=max(0,f[u]-k);
}
int main() {
int n; scanf("%d",&n);
if(n==1) return puts("0"),0;
for(int i=1,u,v;i<n;i++)
scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
int l=1,r=n-1,k,ans;
while(l<=r) {
k=(l+r)/2;
memset(f,0,sizeof(f)), dp(1,0,k);
if(f[1]==0) r=k-1,ans=k;
else l=k+1;
}
printf("%d",ans);
return 0;
}