 /**//*
题意:给出一棵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;
}
|