题意：BOB和ALICE这对狗男女在一颗树上走，BOB先走，BOB要尽量使得总路径权和大，ALICE要小，可是有个条件，就是路径权值总和必须在[L,R]之间，求终于这条路径的权值。

思路：树形dp，dp[u]表示在u结点的权值，往下dfs的时候顺带记录下到根节点的权值总和，然后假设dp[v] + w + sum 在[l,r]内，就是能够的，状态转移方程为

dp[u] = max{dp[v] + w }（bob） dp[u] = min{dp[u] + w} (alice)。所以假设是bob初始化为0，alice初始化为INF。

可是注意假设搜到叶子节点的时候，无论到谁dp[u]都出初始化为0，被这个坑了

还有就是HDU上这题用vector是过不了的，要用数组模拟的链表

代码：

#include <stdio.h>

#include <string.h>

#include <vector>

using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define INF 0x3f3f3f3f

const int N = 500005;

int n, l, r, dp[N], E, first[N], next[N];

struct Edge {

	int u, v, w;

} edge[N];

inline void scanf_(int &num)//无负数

{

    char in;

    while((in=getchar()) > '9' || in<'0') ;

    num=in-'0';

    while(in=getchar(),in>='0'&&in<='9')

        num*=10,num+=in-'0';

}

void dfs(int u, int fa, int sum, int who) {

	if (who && first[u] != -1) dp[u] = INF;

	else dp[u] = 0;

	for (int i = first[u]; i != -1; i = next[i]) {

		int v = edge[i].v, w = edge[i].w;

		if (v == fa) continue;

		dfs(v, u, sum + w, 1 - who);

		if (who == 0 && dp[v] + w + sum >= l && dp[v] + w + sum <= r)

			dp[u] = max(dp[u], dp[v] + w);

		if (who == 1 && dp[v] + w + sum >= l && dp[v] + w + sum <= r)

			dp[u] = min(dp[u], dp[v] + w);

	}

}

void add(int u, int v, int w) {

	edge[E].u = u; edge[E].v = v; edge[E].w = w;

	next[E] = first[u];

	first[u] = E++;

}

int main() {

	while (~scanf("%d%d%d", &n, &l, &r)) {

		E = 0;

		memset(first, -1, sizeof(first));

		int u, v, w;

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

			scanf_(u); scanf_(v); scanf_(w);

			add(u, v, w);

		}

		dfs(0, -1, 0, 0);

		if (dp[0] < l || dp[0] > r) printf("Oh, my god!\n");

		else printf("%d\n", dp[0]);

	}

	return 0;

}