BZOJ 4557 JLoi 2016偵察守備【樹形DP】*

BZOJ 4557 JLoi 2016偵察守備
Description
RさんとBさんはゲームをしています.このゲームの地図はN個の点とN-1個の無方向の辺から構成され、各無方向の辺は2つの点を接続し、地図は連通している.言い換えれば、ゲームの地図はN個のノードがある木です.ゲームには偵察ガードという道具があり、プレイヤーが1つのポイントに偵察ガードを置くと、このポイントとこのポイントとの距離がD以内のすべてのポイントを監視することができます.ここで、2つのポイント間の距離は、ツリー上の距離、すなわち、2つのポイント間の唯一の単純なパスで通過するエッジの数として定義されます.1つの点に偵察守備を置くには一定の代価が必要であり、異なる点に守備を置く代価は異なる可能性がある.今、RさんはすべてのB神が現れる可能性がある位置を知っています.これらの位置を監視する最小の代価を計算してください.
Input
1行目は2つの正の整数NとDを含み、それぞれ地図上の点数と偵察守備の視野範囲を表す.地図上の点を1からNの整数で指定します.2行目N個の正の整数、i個目の正の整数は、iと番号付けされた点に偵察ガードを置く代価Wiを表す.保証Wi≦1000.3行目の正の整数Mは、B神が現れる可能性のある点の数を表す.保証M≦N.4行目のM個の正の整数は、それぞれB神ごとに現れる可能性のある点の番号を表し、小さいときから大きいときまで繰り返し与えない.次のN-1行は、各行に2つの正の整数U、Vを含み、Uと番号が付けられた点とVとの間に無方向のエッジがあることを示す.N<=500000,D<=20
Output
1行に1つの整数で、すべてのB神が現れる可能性のある点を監視するために必要な最小の代価を表します.
Sample Input
12 2 8 9 12 6 1 1 5 1 4 8 10 6 10 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
10
木の上にいくつかの色を染めた点をあげて、それからいくつかの点を選んでマークすることができて、1つのマークした点はそれ自身がdを超えない点をカバーすることができて、それぞれの点に異なる費用があって、すべての染色点をカバーする費用を最小にすることができます
一目で分かるのは木の形DP第二眼がdを見る範囲が20しかない非常に小さい第三眼がNDを発見する時間の複雑さは合理的なようだ.
そして、DPレコードDP配列の構築が開始される:f[i][j]f[i][j]i番ノードのサブツリー内のすべての点が覆われていることを示し、j層を上方に覆うことができる最小費用g[i][j]g[i][j]i番ノードのサブツリー内とi距離がj内の点を除いて、i番ノードのサブツリー内が覆われている最小費用を示す
f[i][0]=g[i][0]f[i]=g[i][0]はfとg配列を変換する際に用いられることが明らかである
また1つの魅力的な性質を発見しました:1つの点iがj層を上に覆うことができることを意味して、この点がj層を下に覆うことができてクラスを分けて討論すればいいことを意味して、またとても証明しやすいです
そして,f[u][i]+g[v][i]f[u]+g[v][i]を用いて,全区間を合法的にカバーする状態を記述することができる.
そして、f[u][i]=min(f[u][i]+g[v][i],g[u][i+1]+f[v][i+1])f[u][i]=m i n(f[u]+g[v][i],g[u][i+1]+f[v][i+1])を明らかにし、jを上に上書きできることに注意して、j-1を上に上書きすることができるので、この関係を利用して更新する.
そしてg配列については,直接加算しましょう.下j層に計算されないことを保証しているからです.

#include
using namespace std;
#define N 500010
#define D 22
#define INF 0x3f3f3f3f
struct Edge{int v,next;}E[N<<1];
int head[N],tot=0;
int n,m,d,w[N];
int f[N][D],g[N][D],dp[N];
int mark[N];
void add(int u,int v){
    E[++tot]=(Edge){v,head[u]};
    head[u]=tot;
}
void dfs(int u,int fa){
    if(mark[u])f[u][0]=g[u][0]=w[u];
    for(int i=1;i<=d;i++)f[u][i]=w[u];
    f[u][d+1]=INF;
    for(int i=head[u];i;i=E[i].next){
        int v=E[i].v;
        if(v==fa)continue;
        dfs(v,u);
        for(int j=d;j>=0;j--)f[u][j]=min(f[u][j]+g[v][j],f[v][j+1]+g[u][j+1]);
        for(int j=d;j>=0;j--)f[u][j]=min(f[u][j],f[u][j+1]);
        g[u][0]=f[u][0];
        for(int j=1;j<=d;j++)g[u][j]+=g[v][j-1];
        for(int j=1;j<=d;j++)g[u][j]=min(g[u][j],g[u][j-1]);
    }
    g[u][d+1]=min(g[u][d+1],g[u][d]);
}
int main(){
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x;scanf("%d",&x);
        mark[x]=1;
    }
    for(int i=1;i
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    printf("%d",f[1][0]);
    return 0;
}