下午组队赛遇到的题，是在hdu上判，一直在超时，各种优化之后还是超时，最后无奈从别人博客上贴代码交，竟然还是超时，但是后来我在uva 上交，我的代码只跑了300多ms，呵呵……，然后我看那个题在hdu上最后一次ac发生在今年1月6号，我也发现还有好多和我有着同样遭遇的，果断放弃，所有下面的代码c++和java都只能在uva 上通过。(之所以要写两遍，是我寄希望于java能通过hdu诡异的测试，但是无果，而且在uva上跑的时间也比较长)。吐槽完还是说题吧。
题意：给一棵n节点的树，每条边都有权值，从根节点走到叶节点，alice希望走的路尽可能短，bob希望走的尽可能长，但是最后走过的路要在l和r之间，bob先走，没人都会做最优选择，问满足条件的最大值。
听说这是一个树形dp，但是我看方法跟我差不多，但是我没感觉是dp呢，可能还是太水。我觉得就是一个dfs，先处理出子每一个子树的状态，bob走时，节点选择子节点到叶节点最大的值，alice走时选择最小，f值为1或-1，用在比较大小的时候，1表示bob走，-1表示alice走，最后对根节点dfs返回的就是最终结果。
c++代码：
#include <string.h> #include <stdio.h> struct edge { int v, l, nxt; }e[500050]; struct node { int mn, e; }id[500050]; int n, l, r, no, tmp; int dfs(int u, int f) { // if(cost > r) return -1; if(id[u].e == -1) { if(id[u].mn >= l && id[u].mn <= r) { return id[u].mn; } return -1; } int t = -1, i; for(i = id[u].e; i != -1; i = e[i].nxt) { id[e[i].v].mn = id[u].mn + e[i].l; tmp = dfs(e[i].v, f * -1); if(tmp != -1) { if(t == -1 || (t - tmp) * f < 0) t = tmp; } } return t; } int main() { int i, j, a, b, c, t; while(~scanf("%d%d%d", &n, &l, &r)) { memset(id, -1, sizeof(id)); no = 0; id[0].mn = 0; for(i = 1; i < n; i++) { scanf("%d%d%d", &a, &b, &c); e[no].v = b; e[no].l = c; e[no].nxt = id[a].e; id[a].e = no++; } t = dfs(0, 1); if(t == -1) printf("Oh, my god!\n"); else printf("%d\n", t); } return 0; } java代码：import java.util.Scanner; class edge{ int v, l, nxt; } public class Main { static int v[]; static edge e[]; static int n, l, r, no; static int dfs(int u, int cost, int f) { if(cost > r) return -1; if(v[u] == -1) { if(cost >= l && cost <= r) return cost; return -1; } int t = -1; for(int i = v[u]; i != -1; i = e[i].nxt) { int tmp = dfs(e[i].v, cost + e[i].l, f * -1); if(tmp != -1) { if(t == -1 || (t - tmp) * f < 0) t = tmp; } } return t; } public static void main(String[] args) { int i, a, b, c; v = new int[500050]; e = new edge[500050]; if(e == null) { System.out.println("WA"); } Scanner in = new Scanner(System.in); while(in.hasNext()) { n = in.nextInt(); l = in.nextInt(); r = in.nextInt(); for(i = 0; i < n; i++) v[i] = -1; no = 0; for(i = 1; i < n; i++) { a = in.nextInt(); b = in.nextInt(); c = in.nextInt(); // System.out.println(a + " " + b + " " + c); e[no] = new edge(); e[no].v = b; e[no].l = c; e[no].nxt = v[a]; // System.out.println(a + " " + b + " " + c); v[a] = no++; } int t = dfs(0, 0, 1); if(t == -1) System.out.println("Oh, my god!"); else System.out.println(t); } in.close(); } }
