#P6939. 地图

    ID: 6770 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF2100提高随机游走首次步分析期望方程期望线性性树形 DP一维前缀和LCA树上倍增

地图

题目描述

有 nn 座城市,由 n−1n-1 条双向道路连成一棵树。第 ii 条道路连接城市 ui,viu_i,v_i,经过它需要 wiw_i 单位时间。

从一个城市开始随机游走。每到一个尚未到达目的地的城市,就在与它相连的道路中等概率选择一条,沿路到达下一个城市。第一次到达目的地时停止。

给定 mm 个询问,每次给出起点 pp 和终点 qq,求游走所花时间的期望值对 109+710^9+7 取模后的结果。

输入格式

第一行两个整数 n,mn,m。接下来 n−1n-1 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,表示一条道路。

接下来 mm 行,每行两个整数 p,qp,q,表示一次询问,保证 p≠qp\ne q。

输出格式

输出 mm 行,每行一个整数,表示对应期望值对 109+710^9+7 取模后的结果。

样例

2 1
1 2 2
1 2
2

数据范围

n,m≤2×105n,m\le2\times10^5,wi≤106w_i\le10^6。

  • 对于 10%10\% 的数据,n≤1000n\le1000。
  • 另有 20%20\% 的数据,树是一条链。
  • 另有 10%10\% 的数据,所有 wi=1w_i=1。

原 PDF 题面