2014
11-30

# Alice and Bob’s Trip

Alice and Bob are going on a trip. Alice is a lazy girl who wants to minimize the total travelling distance, while Bob as an active boy wants to maximize it. At the same time, they cannot let the value to be less than a given integer L since that will make them miss too much pleasure, and they cannot let the value to be greater than a given integer R since they don’t want to get too exhausted.
The city they are visiting has n spots and the spots are connected by directed edges. The spots are connected in such a way that they form a tree and the root will always be at spot 0. They take turns to select which edge to go. Both of them choose optimally. Bob will go first.

There are multiple test cases. For every test case, the first line has three integers, n, L and R (1<=n<=500000, 0<=L, R<=1000000000). The next n-1 lines each has three integers a, b and c, indicating that there is an edge going from spot a to spot b with length c (1<=c<=1000). The spots are labeled from 0 to n-1.
There is a blank line after each test case.
Proceed to the end of file.

There are multiple test cases. For every test case, the first line has three integers, n, L and R (1<=n<=500000, 0<=L, R<=1000000000). The next n-1 lines each has three integers a, b and c, indicating that there is an edge going from spot a to spot b with length c (1<=c<=1000). The spots are labeled from 0 to n-1.
There is a blank line after each test case.
Proceed to the end of file.

3 2 4
0 1 1
0 2 5

7 2 8
0 1 1
0 2 1
1 3 1
1 4 10
2 5 1
2 6 5

7 4 8
0 1 1
0 2 1
1 3 1
1 4 2
2 5 1
2 6 5

4 2 6
0 1 1
1 2 1
1 3 5

Oh, my god!
2
6
2

Alice和Bob两个人从根0出发，轮流选择路径，Bob开始选，在满足总距离在区间【l,r】内，Bob总是选使总距离最大的路径走，Alice总是选使总距离最小的路径走，求最后走的总距离的最大值。

dp[i]表示两人从节点i出发满足各自要求的极值。（对于Bob来说是最大值，对于Alice来说是最小值）。

PS：两人各自的选择标准不一样，dp[i]综合了两个人的选择。有点像对抗搜索。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

#define Maxn 510000
int dp[Maxn],n,l,r,cnt;

struct Edge
{
int v,len,next;
}edge[Maxn];
int head[Maxn];

void add(int a,int b,int c)
{
cnt++;
edge[cnt].v=b,edge[cnt].len=c;
edge[cnt].next=head[a];
head[a]=cnt;
}

void dfs(int cur,int from,int dep)
{
int p=head[cur];
if(!p) //到了叶子节点
{
dp[cur]=0;
return ;
}
dp[cur]=dep?INF:-1; //当前为谁
for(;p;p=edge[p].next)
{
int v=edge[p].v;
dfs(v,from+edge[p].len,dep^1);//先计算叶子节点
if(dp[v]==-1||dp[v]==INF) //叶子节点不满足要求，不走这条路
continue;
int tmp=dp[v]+from+edge[p].len;

if(tmp<=r&&tmp>=l) //满足总体要求
{
if(dep)
dp[cur]=min(dp[cur],dp[v]+edge[p].len);
else
dp[cur]=max(dp[cur],dp[v]+edge[p].len);
}
}
}

int main()
{
while(~scanf("%d%d%d",&n,&l,&r))
{
memset(head,0,sizeof(head));
cnt=0;
for(int i=1;i<n;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
dfs(0,0,0);
//printf("%d\n",dp[0]);
if(dp[0]>=l&&dp[0]<=r)
printf("%d\n",dp[0]);
else
printf("Oh, my god!\n");
}
return 0;
}



1. @黯然过客, 谢谢。虽然我不懂做loader的具体方法与原理，只用nsis简单的打过包，为绿软写必要的注册表和系统文件等，这应该和loader不同。

2. @黯然过客, 谢谢。虽然我不懂做loader的具体方法与原理，只用nsis简单的打过包，为绿软写必要的注册表和系统文件等，这应该和loader不同。

3. @黯然过客, 谢谢。虽然我不懂做loader的具体方法与原理，只用nsis简单的打过包，为绿软写必要的注册表和系统文件等，这应该和loader不同。

4. @黯然过客, 谢谢。虽然我不懂做loader的具体方法与原理，只用nsis简单的打过包，为绿软写必要的注册表和系统文件等，这应该和loader不同。

5. 额楼主能否在发布代码的同时对解题思路做个讲解呢？这样大家在学习的时候就方便多了。

6. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

7. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。