TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3489
  • Problem
  • P3489避难向导
    Limits : Time Limit : 20000 MS   Memory Limit : 165536 KB
    Description

    “特大新闻,特大新闻!全国爆发了一种极其可怕的病毒,已经开始在各个城市中传播开来!全国陷入了巨大的危机!大量居民陷入恐慌,想要逃到其它城市以避难!经调查显示,该病毒来自于C 市的A 学校的一次非法的……”
    “哎。”你关上电视,叹了口气。作为A 学校的校长,你一天前为了保命,独自逃离了A 学校,抛弃了全校师生,包括那个曾经帮你计算并拆除道路的工程师。
    你良心受到了巨大的谴责,因此决定做出一些补救,回答一些逃难的人提出的询问。
    已知该国一共有n 个城市,并且1 号城市是首都。(n-1)条双向的公路连接这些城市,通过这些公路,任意两个城市之间存在且仅存在一条路径。每条公路有一个长度。如果一个城市只与一条公路相连,则称它为边境城市。
    该国政府有一个奇怪的规定:每个城市有一个封闭系数di,定义di 为离这个城市最远的边境城市到这个城市的距离。市民们认为,一个城市的安全系数Si 和它的封闭系数有很重要的联系。a,b,c 是该国的幸运数字,所以大家公认一个城市的安全系数Si = (di + a) * b mod c。
    市民们一共会提出m 次询问。每个询问包含三个信息,xi,yi 和qi。xi 是询问者所在的城市编号。你要为这个询问者在xi 到yi 的必经之路上找出一个离xi最近的避难城市,并且要求这个避难城市的安全系数大于等于qi。如果存在这样的城市(包含xi 和yi),则输出城市编号,否则输出一行包括一个数-1。

    Input Format

    第一行五个数:依次是n, m, a, b, c。
    接下来n-1 行描述公路的信息。每行三个数,前两个数代表这条公路连接的两个城市的编号,第三个数表示这条公路的长度。
    再接下来m 行,每行描述一个询问,包含三个数xi, yi 和qi。

    Output Format

    对于每个询问,输出一行包含一个整数,存在符合要求的城市则输出城市编号,不存在则输出-1。

    Sample Input 1

    7 6 5 6 20
    1 2 4
    2 4 2
    2 5 3
    1 3 5
    3 6 6
    6 7 7
    7 5 15
    3 4 5
    5 4 2
    4 5 2
    6 6 10
    3 5 19

    Sample Output 1

    6
    3
    2
    4
    6
    -1

    Sample Input 2

    30 30 289 207 989
    24 28 1826
    28 21 120
    21 27 85
    28 11 1395
    11 12 226
    12 15 1185
    21 20 353
    12 29 1992
    28 6 1346
    12 14 730
    12 10 1526
    27 22 1426
    22 19 1130
    21 5 1286
    24 8 490
    20 7 550
    12 2 934
    5 13 1160
    21 1 350
    8 23 580
    14 3 1720
    8 16 624
    19 25 1918
    2 4 745
    25 9 1295
    9 17 690
    28 18 1346
    2 30 1886
    11 26 1211
    15 3 575
    3 18 552
    17 15 874
    16 15 621
    26 29 713
    3 3 345
    29 30 782
    3 3 345
    17 3 782
    3 17 782
    16 29 621
    17 3 782
    3 3 345
    3 15 575
    6 26 713
    3 29 487
    17 29 879
    17 23 878
    29 3 485
    29 3 484
    2 1 958
    27 9 587
    1 9 692
    9 26 841
    12 7 956
    19 22 854
    12 18 619
    11 15 934
    13 12 803
    1 24 496

    Sample Output 2

    15
    12
    19
    16
    26
    3
    30
    3
    17
    19
    16
    17
    3
    15
    26
    12
    -1
    -1
    12
    12
    -1
    19
    19
    19
    -1
    19
    -1
    -1
    -1
    -1

    Hint

    【样例解释】
    从城市1 到城市7 的安全系数依次是:18, 2, 8, 14, 0, 18, 0。

    【数据范围】
    对于100%数据, 0<xi, yi<=n<=100000;
    m<=300000
    a,b,c,qi<=1,000,000;
    注意:计算安全系数的中间过程可能需要使用64 位整数。


    Source  by BZ 【2015多校联训5】