hdu - 3660 - Alice and Bobs Trip

題意：一棵有n個結點的樹，編號從0（根結點）開始，Alice和Bob一起從0走到葉子結點，Alice走最短路，Bob走最長路，Bob先選擇下一個結點，然後兩個一起走到那個結點，接著Alice選擇下一個結點……，總長度要在[L, R]內，問這種走法的最長路的長度（1 <= n <= 500000, 0 <= L, R <= 1000000000, 1 <= 相鄰結點間距離 <= 1000）。

——>>怒刷樹狀dp。。。

設da[i]為Alice從結點i出發走到葉子的最短距離，則

狀態轉移方程為：da[x] = min(da[x], db[v[e]] + w[e]);

設db[i]為Bob從結點i出發走到葉子的最長距離，則

狀態轉移方程為：db[x] = max(db[x], da[v[e]] + w[e]);

加上IO優化，以C＋＋提交～

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>

using namespace std;

const int maxn = 500000 + 10;
const int INF = 0x3f3f3f3f;
int n, L, R, head[maxn], nxt[maxn], u[maxn], v[maxn], w[maxn], ecnt, da[maxn], db[maxn];

void init(){
    ecnt = 0;
    memset(head, -1, sizeof(head));
}

void addEdge(int uu, int vv, int ww){
    u[ecnt] = uu;
    v[ecnt] = vv;
    w[ecnt] = ww;
    nxt[ecnt] = head[uu];
    head[uu] = ecnt;
    ecnt++;
}

int nextInt(){
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    int ret = 0;
    while(isdigit(c)){
        ret = ret * 10 + c - '0';
        c = getchar();
    }
    return ret;
}

void read(){
    int uu, vv, ww, i;
    for(i = 0; i < n-1; i++){
        uu = nextInt();
        vv = nextInt();
        ww = nextInt();
        addEdge(uu, vv, ww);
    }
}

void dp(int x, int cur){
    da[x] = head[x] == -1 ? 0 : INF;
    db[x] = 0;
    for(int e = head[x]; e != -1; e = nxt[e]){
        int len = cur + w[e];
        if(len <= R) dp(v[e], len);
        if(len + db[v[e]] >= L && len + db[v[e]] <= R) da[x] = min(da[x], db[v[e]] + w[e]);
        if(len + da[v[e]] >= L && len + da[v[e]] <= R) db[x] = max(db[x], da[v[e]] + w[e]);
    }
}

void solve(){
    dp(0, 0);
    if(db[0]) printf("%d\n", db[0]);
    else puts("Oh, my god!");
}

int main()
{
    while(scanf("%d%d%d", &n, &L, &R) == 3){
        init();
        read();
        solve();
    }
    return 0;
}