NKOJ 3489 Problem（算法与数据结构）

P3489【2015多校联训5】避难向导

问题描述

“重大新闻，重大新闻！全国范围内出现了一种极其危险的病毒，已经蔓延至各个城市！全国正面临前所未有的危机！大量居民陷入极度恐慌，纷纷想要逃往其他城市寻求庇护！根据调查结果，这种病毒源自C市的A学校的一次非法行为……”
“唉。”你关闭电视，长叹一声。作为A学校的校长，你在一天前为了保命，独自离开了A学校，抛弃了全校师生，其中包括那位曾协助你计算并拆除道路的工程师。
此时你的内心充满愧疚与不安，因此决定采取一些补救措施，并回应一些逃难者所提出的疑问。
已知该国共有n个城市，并且1号城市为首都。(n-1)条双向公路连接这些城市，通过这些公路任意两个城市之间仅存在一条唯一的路径。每条公路都有一个特定的长度。如果某个城市仅通过一条公路与其他城市相连，则称其为边境城市。
该国政府设定了一个特殊的规定：每个城市的封闭系数di被定义为从该城市到最远边境城市的距离。市民们认为城市的安全部分与其封闭系数密切相关。由于a、b、c是国家的幸运数字，因此人们普遍接受一个城市的安全部分Si = (di + a) * b mod c 的计算方式。
市民们会提出m次询问。每次询问包含三个信息：xi、yi和qi。xi表示提问者所在的城市编号。你需要在从xi到yi必经之路上找到一个距