 /**//*
題意:給出一棵n個結(jié)點的樹,兩個人一起走,輪流決策 Alice目的是使最后距離最小 Bob相反
問最終走的距離能否滿足區(qū)間[L,R]
(需要走到最后不能走,所以Alice不能不選就結(jié)束了)
如果沒有[L,R],直解dfs,Bob的話選最大兒子走,Alice選最小兒子走
現(xiàn)在多了[L,R],選的時候,就需要判斷滿足總距離(是總距離!!即答案)滿足[L,R]然后再選最大/小
在結(jié)點u判斷選擇是否滿足條件時,需要多記錄一個dist[u]表示從根0到u的距離
if(dist[u] + dp[v] + w <= R && dist[u] + dp[v] + w >= L)
才更新答案
啟示:知道某個節(jié)點,就知道了根0到它的距離以及輪到誰決策
這是很有用的性質(zhì),最終答案就是 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;
}
|