/**//* 题意:给出一棵n个结点的树,两个人一起走,轮流决策 Alice目的是使最后距离最小 Bob相反 问最终走的距离能否满足区间[L,R] (需要走到最后不能走,所以Alice不能不选就结束了) 如果没有[L,R],直解dfs,Bob的话选最大儿子走,Alice选最小儿子走 现在多了[L,R],选的时候,就需要判断满足总距离(是总距离!!即答案)满足[L,R]然后再选最大/小 在结点u判断选择是否满足条件时,需要多记录一个dist[u]表示从根0到u的距离 if(dist[u] + dp[v] + w <= R && dist[u] + dp[v] + w >= L) 才更新答案 启示:知道某个节点,就知道了根0到它的距离以及轮到谁决策 这是很有用的性质,最终答案就是 dist[u]+dp[v]+w */ #include<cstdio> #include<cstring> #include<algorithm> #include<cmath>
using namespace std;
const int MAXN = 500010; const int INF = 1000010000;
struct Node { int v,w; Node *next; };
Node nodes[MAXN],*E[MAXN],*pE; int N,L,R; int dp[MAXN],dist[MAXN];
void init() { for(int i=0;i<N;i++) E[i] = NULL; pE = nodes; }
void add(int u,int v,int w) { pE->v = v; pE->w = w; pE->next = E[u]; E[u] = pE++; }
void dfs(int u,bool who)//true for Bob false for Alice { if(dist[u]>R){dp[u] = 0;return;} int &ans = dp[u]; ans = who?0:INF; if(E[u] == NULL)ans = 0; for(Node *it = E[u];it;it=it->next) { int v = it->v, w = it->w; dist[v] = dist[u] + w; dfs(v,!who); if(dist[u] + dp[v] + w <= R && dist[u] + dp[v] + w >= L) { if(who)ans = max(ans,dp[v]+w); else ans = min(ans,dp[v]+w); } } // if(ans>R) ans = R+10; }
int main() { freopen("in","r",stdin); int a,b,c; while(~scanf("%d%d%d",&N,&L,&R)) { init(); for(int i=1;i<N;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } dfs(0,1); if(dp[0]<=R && dp[0]>=L)printf("%d\n",dp[0]); else puts("Oh, my god!"); } return 0; }
|