#P6939. 地图
地图
题目描述
有 座城市,由 条双向道路连成一棵树。第 条道路连接城市 ,经过它需要 单位时间。
从一个城市开始随机游走。每到一个尚未到达目的地的城市,就在与它相连的道路中等概率选择一条,沿路到达下一个城市。第一次到达目的地时停止。
给定 个询问,每次给出起点 和终点 ,求游走所花时间的期望值对 取模后的结果。
输入格式
第一行两个整数 。接下来 行,每行三个整数 ,表示一条道路。
接下来 行,每行两个整数 ,表示一次询问,保证 。
输出格式
输出 行,每行一个整数,表示对应期望值对 取模后的结果。
样例
2 1
1 2 2
1 2
2
数据范围
,。
- 对于 的数据,。
- 另有 的数据,树是一条链。
- 另有 的数据,所有 。