树形dp！
由于冷大佬的毒奶，我开始刷树形dp了，
先来一到签到题：[POI2011]DYN-Dynamite
我们看到最大值最小，自然地想到二分，我们二分一个最大值，题目就转化为了一个点能覆盖mid范围内的点，求要有几个点能全部覆盖所有的特殊点。想到消防局的设立：但是这道题目又不能那么做。考虑DP，设F[i]表示
以i为根节点的子树中没有被覆盖的最远的点，g[i]表示以i为根的子树中距离i最近的已设立的点（为什么要这么操作?考虑树形dp一般是倒着跑dfs的，我们抉择要不要设立点肯定要考虑距离它最远的未被覆盖的点，而距离该点较远的已设立的点一定已经在之前考虑过了）这有无后效性呢？基于一个贪心：如果F[i]==mid,我们必须选这个点（正确性显然）。最后，如果该点必须要被覆盖但g[i]>mid,我们就要更新一下f[i],最后特判一下根节点。code：
#include#include #include #include #include #include using namespace std;const int maxn=700006;int n,m;bool pan[maxn];struct hzw{ int to,next,v;}e[maxn];int head[maxn],cur,tot,noc[maxn],hc[maxn];inline void add(int a,int b){ e[cur].to=b; e[cur].next=head[a]; head[a]=cur++;}inline void dfs(int s,int k,int fa){ noc[s]=-0x3f3f3f3f,hc[s]=0x3f3f3f3f; for (int i=head[s];i!=-1;i=e[i].next) { if (e[i].to==fa) continue; dfs(e[i].to,k,s); noc[s]=max(noc[s],noc[e[i].to]+1); hc[s]=min(hc[s],hc[e[i].to]+1); } if (pan[s]&&hc[s]>k) noc[s]=max(noc[s],0); if (hc[s]+noc[s]<=k) noc[s]=-0x3f3f3f3f; if (noc[s]==k) {tot++;hc[s]=0,noc[s]=-0x3f3f3f3f;}}inline bool check(int mid){ tot=0; dfs(1,mid,1); if (noc[1]>=0) tot++; return tot<=m;}int main(){ memset(head,-1,sizeof(head)); cin>>n>>m; for (int i=1;i<=n;++i) scanf("%d",&pan[i]); for (int i=1,a,b;i<=n-1;++i) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } int l=0,r=n,ans=n; while (l<=r) { int mid=(l+r)>>1; if (check(mid)) { r=mid-1; ans=min(ans,mid); } else { l=mid+1; } } cout<