题意：一棵有n个结点的树，编号从0（根结点）开始，Alice和Bob一起从0走到叶子结点，Alice走最短路，Bob走最长路，Bob先选择下一个结点，然后两个一起走到那个结点，接着Alice选择下一个结点……，总长度要在[L, R]内，问这种走法的最长路的长度（1 <= n <= 500000, 0 <= L, R <= 1000000000, 1 <= 相邻结点间距离 <= 1000）。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3660
——>>怒刷树状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;
}