大佬博客链接:http://blog.csdn.net/shuangde800/article/details/9974599
题意
给一棵n个结点的树，结点编号为0~n-1,顶点是0每条边都有一个权值。
Alice和Bob初始位置在顶点，要往下一直走到叶子结点。
第一次是由Bob选择走向哪个子结点，第二次轮到Alice，依次轮流下去...
每走过一条边就会获得相应的权值，Bob希望所走的路径总权值越大越好，而Alice希望越小越好
每次他们都会选择最优解。
最终总权值要在范围[L,R]之内。
问最终Bob希望的最大权值是多少？
思路
dp(u, 0)表示第u点由Bob选时的最大值dp(u, 1)表示第u点由Alice选时的最大值
tot(u) 表示由顶点走到i点的权值之和
w(u,v)表示连接点u和v的边的权值
那么
dp(u, 0) = max{ dp(v, 1) + w(u,v) | v是u的儿子结点 && L <= dp(v,1)+w(u)+tot(u) <= R}
dp(u, 1) = min{ dp(v, 0) + w(u,v) | v是u的儿子结点 && L <= dp(v,0)+w(u)+tot(u) <= R}
最终答案为f(0, 0)
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 500010;
int head[MAXN], tol;
int n, l, r;
int dp[MAXN][2];
struct Edge
{int to, w, nxt;
} edge[MAXN];
inline void addedge(int u, int v, int w)
{edge[tol].to = v;edge[tol].w = w;edge[tol].nxt = head[u];head[u] = tol++;
}
inline void init()
{tol = 0;memset(head, -1 , sizeof(head));
}
inline bool check(int sum)
{return sum >= l && sum <= r;
}
void dfs(int u, int tot)
{dp[u][0] = 0;dp[u][1] = head[u] == -1 ? 0:INF;for(int i = head[u]; i != -1; i = edge[i].nxt){int v = edge[i].to;int w = edge[i].w;dfs(v, tot+w);if(check(tot+w+dp[v][1]))dp[u][0] = max(dp[u][0], dp[v][1] + w);if(check(tot+w+dp[v][0]))dp[u][1] = min(dp[u][1], dp[v][0] + w);}
}
int main()
{while(~scanf("%d%d%d", &n, &l, &r)){init();for(int i = 0; i < n-1; i++){int u, v, w;scanf("%d%d%d", &u, &v, &w);addedge(u, v, w);}dfs(0, 0);//if (!check(dp[0][0]))if (!dp[0][0])puts("Oh, my god!");elseprintf("%d\n", dp[0][0]);}return 0;
}