企业网站建设有哪些/推广哪个app最挣钱

Description

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

Input

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

Output

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

Sample Input

4 2
1 2
2 3
3 4
1 4
3 4

Sample Output

9
5 

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 <iostream>
#include <cstdio>
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<n;i++) {int u,v;scanf("%d%d",&u,&v);Add(u,v);Add(v,u);}Dfs_F(1,0);f1[1]=f2[1]=0;Dfs_G(1,0);Dfs_Get(1,0);for (int i=1;i<=19;i++)for (int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1];for (int i=0;i<q;i++) {int u,v;scanf("%d%d",&u,&v);int lca=Lca(u,v);printf("%lld\n",((f1[u]-f1[lca]+f2[v]-f2[lca])%P+P)%P);}fclose(stdin);fclose(stdout);
}