动态规划（树形DP）：LNOI 2016 侦察守卫

Sample Input

12 2

8 9 12 6 1 1 5 1 4 8 10 6

1 2 3 5 6 7 8 9 10 11

1 3

2 3

3 4

4 5

4 6

4 7

7 8

8 9

9 10

10 11

11 12

Sample Output

　　这道题考虑树形DP，dp[x][i]表示由此点向下走i步到达的点监控，由于有的点不需要被监控，再开一个变量记录即可，转移并不复杂，推一推就出来了。

　　可能我的代码有瑕疵，有些地方可能不必要（毕竟DP有时候想不清），但是不影响正确性。

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #define dp(x,y) dp[x][y+20]
  5 using namespace std;
  6 const int N=500010,D=21,INF=100000000;
  7 int n,m,d,w[N],dp[N][D*2],f[N];bool vis[N];
  8 int cnt,fir[N],to[N*2],nxt[N*2];
  9 void addedge(int a,int b){
 10     nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;
 11     nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;
 12 }
 13 
 14 int st[N],top;
 15 int m1[N],m2[N];
 16 void DP(int x,int fa){
 17     int flag=0;
 18     for(int i=fir[x];i;i=nxt[i])
 19         if(to[i]!=fa)flag=1,DP(to[i],x);
 20     
 21     if(!flag){
 22         f[x]=vis[x]?INF:0;dp(x,0)=w[x];
 23         for(int i=1;i<=d;i++)dp(x,i)=INF;
 24         return;
 25     }
 26     
 27     top=0;
 28     for(int i=fir[x];i;i=nxt[i])
 29         if(to[i]!=fa)st[++top]=to[i];
 30     
 31     //处理f[x]
 32     if(!vis[x])
 33     for(int i=1,M;i<=top;i++){
 34         M=f[st[i]];
 35         for(int j=0;j<=d;j++)
 36             M=min(M,dp(st[i],j));
 37         f[x]+=M;    
 38     }
 39     else f[x]=INF;
 40     
 41     //处理dp(x,0)
 42     dp(x,0)=w[x];
 43     for(int i=1,M;i<=top;i++){
 44         M=f[st[i]];
 45         for(int j=-d;j<=d;j++)
 46             M=min(M,dp(st[i],j));
 47         dp(x,0)+=M;    
 48     }
 49     
 50     //处理向上看的
 51     for(int i=1;i<=top;i++){
 52         m2[i]=f[st[i]];
 53         for(int j=0;j<=d;j++)
 54             m2[i]=min(m2[i],dp(st[i],j));
 55         m1[i]=INF;
 56     }
 57     
 58     for(int i=-d;i<=-1;i++)
 59         for(int j=1;j<=top;j++){
 60             dp(x,i)+=min(m1[j],m2[j]);
 61             m1[j]=min(m1[j],dp(st[j],i));
 62         }
 63     
 64     //处理向下看的
 65     for(int i=1;i<=top;i++){
 66         m2[i]=f[st[i]];
 67         for(int j=0;j<=d;j++)
 68             m2[i]=min(m2[i],dp(st[i],j));
 69         m1[i]=INF;
 70     }
 71     
 72     for(int i=d,M;i>=1;i--){
 73         M=-INF;
 74         for(int j=1;j<=top;j++){
 75             dp(x,i)+=min(m1[j],m2[j]);
 76             M=max(M,min(m1[j],m2[j])-dp(st[j],i-1));
 77             m1[j]=min(m1[j],dp(st[j],-i));
 78         }
 79         dp(x,i)-=M;
 80     }
 81 }
 82 
 83 
 84 int main(){
 85     freopen("observer.in","r",stdin);
 86     freopen("observer.out","w",stdout);
 87     scanf("%d%d",&n,&d);
 88     for(int i=1;i<=n;i++)
 89         scanf("%d",&w[i]);
 90     scanf("%d",&m);
 91     for(int i=1,x;i<=m;i++){
 92         scanf("%d",&x);
 93         vis[x]=true;
 94     }    
 95     for(int i=1,a,b;i<n;i++){
 96         scanf("%d%d",&a,&b);
 97         addedge(a,b);
 98     }
 99     DP(1,1);
100     int ans=f[1];
101     for(int i=0;i<=d;i++)
102         ans=min(ans,dp(1,i));
103     printf("%d
",ans);    
104     return 0;
105 }