Fire (poj 2152 树形dp)

给定一棵n个结点的树（1<n<=1000）。现在要选择某些点，使得整棵树都被覆盖到。当选择第i个点的时候，可以覆盖和它距离在d[i]之内的结点，同时花费为v[i]。问最小花费。

以前做过一道类似的题（水库），这道题也差不多。首先来考虑，用\(best[i]\)表示以i为根的子树的最小花费。这样做有什么问题呢？它无法很好的处理消防站重复建的问题。

所以换一种做法。\(best[i]\)依然表示原来的含义，新建一个数组\(f[i][j]\)，表示当i这个结点，依赖j的消防站时的最小花费。转移方程就是：\(f[i][j]=v[i]+\sum min(f[son_k][j]-v[j], best[son_k])\)。注意当\(dis(i, j)>d[i]\)时，\(f[i][j]=\infty\)。它的思想就是如果i依赖j，就直接让子树中依赖j的点都减去依赖，从而消除影响。

(傻逼了，用rmq求树上两点距离)

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=1005, maxm=1005, logn=12, INF=1e9;

struct Graph{

    struct Edge{

        int to, next, v; Graph *bel;

        inline int operator*(){ return to; }

        Edge& operator ++(){

            return *this=bel->edge[next]; }

    }edge[maxm*2];

    void reset(){

        memset(fir, 0, sizeof(fir)); cntedge=0; }

    void addedge(int x, int y, int v){

        Edge& e=edge[++cntedge];

        e.to=y; e.next=fir[x]; e.v=v;

        e.bel=this; fir[x]=cntedge; }

    Edge& getlink(int x){ return edge[fir[x]]; }

    int cntedge, fir[maxn];

}g;

//初始化及树形dp

int T, n, mi[logn], w[maxn], d[maxn];

int best[maxn], dp[maxn][maxn];

//求两点距离(rmq lca)

int id[maxn*2], fir[maxn], dep[maxn], time;

int st[maxn*2][logn];

void predfs(int now, int par){

    Graph::Edge e=g.getlink(now);

    id[++time]=now; fir[now]=time;

    for (; *e; ++e){

        if (*e==par) continue;

        dep[*e]=dep[now]+e.v; predfs(*e, now);

        id[++time]=now;

    }

}

int mindep(int x, int y){

    return (dep[x]<dep[y])?x:y; }

void init_st(){

    for (int i=1; i<=n*2; ++i) st[i][0]=id[i];

    for (int i=1; i<logn; ++i)

        for (int j=1; j<=n*2; ++j) if (j+mi[i]-1<=n*2)

            st[j][i]=mindep(st[j][i-1], st[j+mi[i-1]][i-1]);

}

int log2(float x){

    return ((unsigned&)x>>23&255)-127;

}

int getlca(int x, int y){

    if (fir[x]>fir[y]) swap(x, y);

    int fx=fir[x], fy=fir[y];

    int logxy=log2(fy-fx+1);

    return mindep(st[fx][logxy],

                  st[fy-mi[logxy]+1][logxy]);

}

int dis(int x, int y){

    int lca=getlca(x, y);

    return dep[x]+dep[y]-2*dep[lca];

}

void dfs(int now, int par){

    Graph::Edge e=g.getlink(now);

    for (; *e; ++e) if (*e!=par) dfs(*e, now);

    e=g.getlink(now); best[now]=INF;

    for (int j=1; j<=n; ++j)

        dp[now][j]=(dis(now, j)<=d[now]?w[j]:INF);

    for (; *e; ++e) if (*e!=par)

        for (int j=1; j<=n; ++j) if (dis(now, j)<=d[now])

            dp[now][j]+=min(dp[*e][j]-w[j], best[*e]);

    for (int j=1; j<=n; ++j)

        best[now]=min(best[now], dp[now][j]);

}

int main(){

    scanf("%d", &T); int x, y, l;

    mi[0]=1; for (int i=1; i<logn; ++i) mi[i]=mi[i-1]*2;

    while (T--){

        g.reset(); scanf("%d", &n);

        for (int i=1; i<=n; ++i) scanf("%d", &w[i]);

        for (int i=1; i<=n; ++i) scanf("%d", &d[i]);

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

            scanf("%d%d%d", &x, &y, &l);

            g.addedge(x, y, l); g.addedge(y, x, l);

        }

        time=0; predfs(1, 0); dep[1]=0;

        init_st(); dfs(1, 0);

        printf("%d\n", best[1]);

    }

    return 0;

}