【题意】：给出一棵n个结点的有向树，两个人一起走，轮流决策，Alice的目的是使最后的距离最小，Bob的目的是使最后的距离最大。问最后的距离能否满足在区间[L,R]。需要走到不能走的地方才能停。
【题解】：这题要注意的是，可能还没有走到叶子结点就停止了。
然后就是一个树形dp。
对于一棵给定的树，每个结点轮到谁决策是确定的。
根据当前不同的人，选择满足当前区间[L',R']最大值或者最小值。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 #define maxm 600000
22 #define maxn 505000
23
24 int n, L, R;
25 int tot, eh[maxn];
26 int dp[maxn];
27
28 struct Edge {
29 int v, w, next;
30 }et[maxm];
31
32 void init() {
33 tot = 0;
34 memset(eh, -1, sizeof(eh));
35 }
36
37 void addedge(int u, int v, int w) {
38 Edge e = {v, w, eh[u]};
39 et[tot] = e;
40 eh[u] = tot++;
41 }
42
43 void dfs(int u, int L, int R, int flag) {
44 dp[u] = 0;
45 for(int i = eh[u]; i != -1; i = et[i].next) {
46 int v = et[i].v, w = et[i].w;
47 dfs(v, L - w, R - w, !flag);
48 if(dp[v] + w >= L && dp[v] + w <= R) {
49 if(dp[u] == 0) dp[u] = dp[v] + w;
50 else {
51 if(flag) dp[u] = max(dp[u], dp[v] + w);
52 else dp[u] = min(dp[u], dp[v] + w);
53 }
54 }
55 }
56 }
57
58 int main() {
59 int u, v, w;
60 while(~scanf("%d%d%d", &n, &L, &R)) {
61 init();
62 for(int i = 1; i < n; i++) {
63 scanf("%d%d%d", &u, &v, &w);
64 addedge(u, v, w);
65 }
66 dfs(0, L, R, 1);
67 if(R < L || dp[0] < L || dp[0] > R) printf("Oh, my god!\n");
68 else printf("%d\n", dp[0]);
69 }
70 return 0;
71 }
72