Description

梦游中的你来到了一棵 N 个节点的树上. 你一共做了 Q 个梦, 每个梦需要你从点 u 走到 点 v 之后才能苏醒, 由于你正在梦游, 所以每到一个节点后,你会在它连出去的边中等概率地 选择一条走过去, 为了确保第二天能够准时到校, 你要求出每个梦期望经过多少条边才能苏 醒. 为了避免精度误差, 你要输出答案模10^9 + 7的结果.

 

Input

第一行两个整数分别代表 N 和 Q. 接下来 N-1 行, 每行两个整数 u, v 代表树中的一条边. 接下来 Q 行, 每行两个整数代表询问的 u,v. 

Output

一共 Q 行, 每行一个整数代表答案

 

Sample Input

4 21 22 33 41 43 4

Sample Output

95 

 

Data Constraint

对于 20%的数据, N <= 10.

对于 40%的数据, N <= 1000.

另有 20%的数据, 保证给定的树是一条链.

对于 100%的数据, N <= 100000, Q <= 100000. 

 

Hint

分析

我们可以设f1[i]为i走到它父亲的期望边数，f2[i]表示它父亲走到i的期望边数，那么：

对于f1

1/deg[i]+∑(f1[son]+f1[i]+1) /deg[i]→f1[i]

化简式子：

1+∑(f1[son]+f1[i]+1)→f1[i]*deg[i]

1+∑f1[son] +deg[i]-1+(deg[i]-1)*f1[i]→f1[i]*deg[i]

deg[i]+∑f1[son]→f1[i]

对于f2

1/deg[father]+(1+f2[i]+f2[father])/deg[father]+∑_(son≠i)(1+f2[i]+f1[son]) /deg[father]→f2[i]

1+1+f2[i]+f2[father]+∑_(son≠i)(1+f2[i]+f1[son])→f2[i]*deg[i]

2+f2[i]+f2[father]+deg[i]-2+(deg[i]-2)*f2[i]+∑f1[son]→f2[i]*deg[i]

deg[i]+f2[father]+∑f1[son]→f2[i]

预处理出来，跑LCA就行了

#include 
      
       #include 
       
        using namespace std;typedef long long ll;const int N=1e5+1;const ll P=1e9+7;struct Edge {    int u,v,nx;}g[2*N];int cnt,list[N],deg[N],dep[N];ll f1[N],f2[N],f[N][20];int n,q;void Add(int u,int v) {g[++cnt].u=u;g[cnt].v=v;g[cnt].nx=list[u];list[u]=cnt;deg[u]++;}void Dfs_F(int u,int fa) {    f1[u]=deg[u];    for (int i=list[u];i;i=g[i].nx)    if (g[i].v!=fa) {        Dfs_F(g[i].v,u);        (f1[u]+=f1[g[i].v])%=P;    }}void Dfs_G(int u,int fa) {    int sum=deg[u];    for (int i=list[u];i;i=g[i].nx)    if (g[i].v!=fa) (sum+=f1[g[i].v])%=P;    else (sum+=f2[u])%=P;    for (int i=list[u];i;i=g[i].nx)    if (g[i].v!=fa) {        f2[g[i].v]=((sum-f1[g[i].v])%P+P)%P;        Dfs_G(g[i].v,u);    }}void Dfs_Get(int u,int fa) {    dep[u]=dep[fa]+1;f[u][0]=fa;    (f1[u]+=f1[fa])%=P;(f2[u]+=f2[fa])%=P;    for (int i=list[u];i;i=g[i].nx)    if (g[i].v!=fa) Dfs_Get(g[i].v,u);}int Lca(int a,int b) {    if (dep[a]>dep[b]) swap(a,b);    for (int i=19;i>=0;i--)    if (dep[f[b][i]]>=dep[a]) b=f[b][i];    if (a==b) return a;    for (int i=19;i>=0;i--)    if (f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];    return f[a][0];}int main() {    freopen("tree.in","r",stdin);    freopen("tree.out","w",stdout);    scanf("%d%d",&n,&q);    for (int i=1;i