题解 P3554 【[POI2013]LUK-Triumphal arch】
_lgswdn
2020-05-08 13:06:12
### [$\texttt{POI-Triumphal arch}$](https://www.luogu.com.cn/problem/P3554)
由于一旦 B 进入了一个子树，那么他就不会出来（因为不会免费赠送 A 一个涂色的机会）。所以这个问题仍然适用和子树相关的树形 $dp$。
我们对 $k$ 进行二分答案。
对于一个节点 $u$，如果 B 走到了 $u$，那么在下一步前必须保证 $u$ 的所有儿子节点都被染色。完成染色有两种方法：第一种，在下一步前赶快把这几个点全部染上；第二种，在 B 走到 $u$ 前就染上这里的一些点。当然，如果可以选择第一种，那么就没有必要选择第二种，我们总是希望可以独立完成任务然后造福后人。
所以我们可以设立状态，表示这个节点需要自己的祖先提前染色多少节点才能覆盖住整个子树。
最终要求根节点为 $0$。
对于转移，一个节点需要的，即给自己的儿子节点染色所需要的和来自自己儿子子树的求助。因为儿子没法帮助祖先，所以如果发现自己还有很多空余的染色机会没用或者正好用完，那么 $f_u=0$
要注意 $n=1$ 时需要特判。
```cpp
#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;
}
```