解题：POI 2011 Dynamite

题面

从零开始的DP学习系列之叁

树形DP的基本(常见？)思路：先递归进儿子，然后边回溯边决策，设状态时常设$dp[x]$表示以$x$为根的子树中(具体分析算不算$x$这个点)的情况

显然的二分答案，之后问题转化为用$m$个能覆盖$mid$范围的点能否覆盖所有的特殊点，用树形DP判断

设$unc[nde]$表示以$nde$为根(包含$nde$)的子树中最远的未被覆盖的特殊点的距离，$cov[nde]$以$nde$为根(包含$nde$)的子树中最近的选出的点的距离。有两个从儿子$goal[i]$获取信息的显然的转移

unc[nde]=max(unc[nde],unc[goal[i]]+);

cov[nde]=min(cov[nde],cov[goal[i]]+);

然后考虑对点的选择，首先如果这个点是特殊点，而且$cov[nde]>mid$，说明这个点无法被子树中的点覆盖，只能交给父亲处理，于是更新一下它的$unc$的信息，告诉它的父亲考虑这个点

if(imp[nde]&&cov[nde]>mid) unc[nde]=max(unc[nde],);

接下来考虑这个点的子树中的特殊点(们)能否靠这个点解决，如果$unc[nde]+cov[nde]<=mid$说明这个子树不需要父亲管了

if(unc[nde]+cov[nde]<=mid) unc[nde]=-inf;

最后是考虑是否选择这个点，这里贪心考虑，只在$unc$正好等于$mid$时选择这个点

if(unc[nde]==mid) unc[nde]=-inf,cov[nde]=,tot++;

注意的是根节点没有父亲，要特殊考虑

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=,inf=0x3f3f3f3f;

 int p[N],noww[*N],goal[*N];

 int imp[N],unc[N],cov[N];

 int n,m,t1,t2,cnt,tot,l,r,mid,ans;

 void link(int f,int t)

 {

     noww[++cnt]=p[f];

     goal[cnt]=t,p[f]=cnt;

 }

 void DFS(int nde,int fth)

 {

     unc[nde]=-inf,cov[nde]=inf;

     for(int i=p[nde];i;i=noww[i])

         if(goal[i]!=fth)

         {

             DFS(goal[i],nde);

             unc[nde]=max(unc[nde],unc[goal[i]]+);

             cov[nde]=min(cov[nde],cov[goal[i]]+);

         }

     if(imp[nde]&&cov[nde]>mid) unc[nde]=max(unc[nde],);

     if(unc[nde]+cov[nde]<=mid) unc[nde]=-inf;

     if(unc[nde]==mid) unc[nde]=-inf,cov[nde]=,tot++;

 }

 bool check(int x)

 {

     tot=; DFS(,);

     return tot+(unc[]>=)<=m;

 }

 int main ()

 {

     scanf("%d%d",&n,&m),r=n;

     for(int i=;i<=n;i++)

         scanf("%d",&imp[i]);

     for(int i=;i<n;i++)

     {

         scanf("%d%d",&t1,&t2);

         link(t1,t2),link(t2,t1);

     }

     while(l<=r)

     {

         mid=(l+r)/;

         if(check(mid)) r=mid-,ans=mid;

         else l=mid+;

     }

     printf("%d",ans);

     return ;

 }