uva 1484 Alice and Bobs Trip （樹形dp）

題目來源： UVA    HDU 

題意
給一棵n個結點的樹，結點編號為0~n-1,頂點是0
每條邊都有一個權值。
Alice和Bob初始位置在頂點，要往下一直走到葉子結點。
第一次是由Bob選擇走向哪個子結點，第二次輪到Alice，依次輪流下去...
每走過一條邊就會獲得相應的權值，Bob希望所走的路徑總權值越大越好，而Alice希望越小越好
每次他們都會選擇最優解。
最終總權值要在范圍[L,R]之內。
問最終Bob希望的最大權值是多少？

思路
f(u, 0)表示第u點由Bob選時的最大值

f(u, 1)表示第u點由Alice選時的最大值

tot(u) 表示由頂點走到i點的權值之和

w(u,v)表示連接點u和v的邊的權值

那麼
f(u, 0) = max{ f(v, 1) + w(u,v) | v是u的兒子結點 && L <= f(v,1)+w(u)+tot(u) <= R}
f(u, 1) = min{ f(v, 0) + w(u,v) | v是u的兒子結點 && L <= f(v,0)+w(u)+tot(u) <= R}

最終答案為f(0, 0)

另外，這題在HDU題提交時，用C++可以AC，但是用G++卻TLE了，不知為什麼。

代碼

/**========================================== *


   This is a solution for ACM/ICPC problem * * 
  @source：uva-148
4 Alice and Bob's Trip  *   
@type: 樹形dp *   @author: shuangde *  
 @blog: blog.csdn.net/shuangde800 * 
  @email: zengshuangde@gmail.com *
===========================================*/
#include<iostream>#include<cstdio>#include<algorithm>#include<vector>
#include<queue>#include<cmath>#include<cstring>typedef long long int64;
const int INF = 0x3f3f3f3f;const double PI  = acos(-1.0);
const int MAXN = 500010;
namespace Adj{    int head[MAXN];  
  int size; 
   struct Node{        int v, w, next;  
  }E[MAXN]; 
   inline void initAdj() {   
     size = 0;    
    memset(head, -1, sizeof(head)); 
   }    inline void addEdge(int u, int v, int w) {        E[size].v = v;   
     E[size].w = w;   
     E[size].next = head[u];   
     head[u] = size++;  
  }}using namespace Adj;
using namespace std;int n, l, r;
int f[MAXN][2];
int dist[MAXN];
inline bool check(int sum) {    return sum >=l && sum <= r;
}void dfs(int u, int tot) {    f[u][0] = 0;   
  f[u][1] = head[u]==-1?0:INF; 
    for(int e = head[u]; 
e!=-1;
 e = E[e].next) {        int v = E[e].v;  
      int w = E[e].w;      
  dfs(v, tot+w);   
     if(check(tot+w+f[v][1])) {            f[u][0] = max(f[u][0], w+f[v][1]);   
         }        if(check(tot+w+f[v][0])) {            f[u][1] = min(f[u][1], w+f[v][0]);   
        }    }}// 讀入加速  inline int nextInt() {      char c = getchar();   
   while (!isdigit(c)) c = getchar(); 
    int x = 0;   
 while (isdigit(c)) {          x = x*10+c-'0';   
       c = getchar();      }      return x; 
 }int main(){    while (~scanf("%d%d%d", &n, &l, &r)) {        initAdj();     
   for (int i = 0;
 i < n - 1; ++i) {            int u, v, w;   
         u = nextInt();   
        v = nextInt();   
         w = nextInt();  
          addEdge(u,v,w);     
   }        dfs(0, 0);      
  if (!check(f[0][0])) {            puts("Oh, my god!");   
     } else {            printf("%d\n", f[0][0]);    
    }    }    return 0;}