Description：

在一棵 $n$ 个节点的树上在每个点向每条出边等概率随机走，多次询问从点 $a$ 走到点 $b$ 的期望。

$1\le n \le 10^5$ $1\le q \le 10^5$

Solution：

记 $u[i]$ 为 $i$ 走到他父亲的期望步数， $d[i]$ 为 $i$ 从他父亲走过来的期望步数。

若 $i$ 为叶子， $u[i]=1$ ，若 $i$ 为根， $u[i] = 0,d[i]=0$ 。

$\begin{align}u[k]=\frac1{deg[k]}+\sum_{i是k的子节点}\frac{u[i]+1+u[k]}{deg[k]}\end{align}$

$\begin{align}d[k]=\frac{1}{deg[fa[k]]}+\frac{1+d[fa[k]]+d[k]}{deg[fa[k]]}+\sum_{i是fa[k]的子节点.i\ne k}\frac{1+u[i]+d[k]}{deg[fa[k]]}\end{align}$

移一下项就能求出所有的 $u$ 和 $d$ ，预处理三个倍增数组，每次询问时由于期望具有线性性所以可以直接把两条路径上的 $u$ 和 $d$ 加和即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 100010

int deg[MAXN];

#define MOD 1000000007

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++deg[a];++deg[b];

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int u[MAXN][18],d[MAXN][18];

int sum[MAXN];

int f[MAXN][18];

bool v[MAXN];

int dep[MAXN];

void dp1(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		f[e[i].to][0] = k;

		dep[e[i].to] = dep[k] + 1;

		dp1(e[i].to);

		sum[k] += u[e[i].to][0];

	}

	u[k][0] = deg[k] + sum[k];

	v[k] = false;

	return;

}

void dp2(int k)

{

	v[k] = true;

	d[k][0] = d[f[k][0]][0] + deg[f[k][0]] + sum[f[k][0]] - u[k][0];

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp2(e[i].to);

	}

	v[k] = false;

	return;

}

int query(int a,int b)

{

	int res = 0;

	for(int i = 17;i >= 0;--i)

	{

		if(dep[f[a][i]] >= dep[b])

		{

			res += u[a][i];

			a = f[a][i];

			res %= MOD;

		}

	}

	for(int i = 17;i >= 0;--i)

	{

		if(dep[f[b][i]] >= dep[a])

		{

			res += d[b][i];

			b = f[b][i];

			res %= MOD;

		}

	}

	if(a == b)return res;

	for(int i = 17;i >= 0;--i)

	{

		if(f[a][i] != f[b][i])

		{

			res += u[a][i];a = f[a][i];

			res += d[b][i];b = f[b][i];

			res %= MOD;

		}

	}

	res += u[a][0] + d[b][0];

	res %= MOD;

	return res;

}

int main()

{

	freopen("tree.in","r",stdin);

	freopen("tree.out","w",stdout);

	scanf("%d%d",&n,&q);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dep[1] = 1;

	dp1(1);u[1][0] = 0;

	dp2(1);

	for(int k = 1;k <= 17;++k)

	{

		for(int i = 1;i <= n;++i)

		{

			f[i][k] = f[f[i][k - 1]][k - 1];

			u[i][k] = (u[i][k - 1] + u[f[i][k - 1]][k - 1]) % MOD;

			d[i][k] = (d[i][k - 1] + d[f[i][k - 1]][k - 1]) % MOD;

		}

	}

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		printf("%d\n",query(a,b));

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}