TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3489
  • 题目
  • P3489【2015多校联训5】避难向导
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    问题描述

    “特大新闻,特大新闻!全国爆发了一种极其可怕的病毒,已经开始在各个城市中传播开来!全国陷入了巨大的危机!大量居民陷入恐慌,想要逃到其它城市以避难!经调查显示,该病毒来自于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。

    输入格式

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

    输出格式

    对于每个询问,输出一行包含一个整数,存在符合要求的城市则输出城市编号,不存在则输出-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

    样例输出

    6
    3
    2
    4
    6
    -1

    提示

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

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


    来源  by BZ