首页 > 代码库 > BZOJ4557 侦察守卫

BZOJ4557 侦察守卫

题解:

和HDU5290很像,但是hdu挂了,等好了再来补这个题

不是太懂啊。。。

看了题解也不懂。。。。。

等做了HDU2590再来看看这题

代码:

//http://blog.csdn.net/aarongzk/article/details/51703297//http://blog.csdn.net/ziqian2000/article/details/52334662#include<bits/stdc++.h>using namespace std;#define pb push_back#define mp make_pair#define se second#define fs first#define LL long long#define CLR(x) memset(x,0,sizeof x)#define MC(x,y) memcpy(x,y,sizeof(x))  #define SZ(x) ((int)(x).size())#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1 typedef pair<int,int> P;const double eps=1e-9;const int maxn=500100;const int mod=1e9+7;const int INF=1e9;int w[maxn],b[maxn],head[maxn];int down[maxn][25],up[maxn][25];int n,d,k,cnt,q;//down[i][j]表示以i为根的子树中,向下前j层的最小花费//up[i][j]表示以i为根的子树中,向上j层被覆盖,其子树满足条件的最小花费 struct Edge{    int v,nxt;}edge[maxn*2];void AddEdge(int u,int v){    edge[cnt].v=v;    edge[cnt].nxt=head[u];    head[u]=cnt++;}void dfs(int u,int fa){    if(b[u]) down[u][0]=up[u][0]=w[u];    for(int i=1;i<=d;i++) up[u][i]=w[u];    up[u][d+1]=INF;    for(int i=head[u];i!=-1;i=edge[i].nxt){        int v=edge[i].v;        if(v==fa) continue;        dfs(v,u);        for(int j=0;j<=d;j++) up[u][j]=min(up[u][j]+down[v][j],up[v][j+1]+down[u][j+1]);        for(int j=d;j>=0;j--) up[u][j]=min(up[u][j],up[u][j+1]);        down[u][0]=up[u][0];        for(int j=1;j<=d;j++) down[u][j]+=down[v][j-1];        for(int j=1;j<=d;j++) down[u][j]=min(down[u][j-1],down[u][j]);    }}int main(){    cnt=0;    memset(head,-1,sizeof(head));    scanf("%d%d",&n,&d);    for(int i=1;i<=n;i++) scanf("%d",&w[i]);    scanf("%d",&k);    for(int i=1;i<=k;i++){        scanf("%d",&q);        b[q]=1;    }    for(int i=1;i<=n-1;i++){        int x,y;        scanf("%d%d",&x,&y);        AddEdge(x,y);AddEdge(y,x);    }    dfs(1,-1);    printf("%d\n",down[1][0]);    return 0;}

 

BZOJ4557 侦察守卫