Title
题目描述
梦游中的你来到了一棵 N 个节点的树上. 你一共做了 Q 个梦, 每个梦需要你从点 u 走到 点 v 之后才能苏醒, 由于你正在梦游, 所以每到一个节点后,你会在它连出去的边中等概率地 选择一条走过去, 为了确保第二天能够准时到校, 你要求出每个梦期望经过多少条边才能苏 醒. 为了避免精度误差, 你要输出答案模10^9 + 7的结果.
输入
第一行两个整数分别代表 N 和 Q. 接下来 N-1 行, 每行两个整数 u, v 代表树中的一条边. 接下来 Q 行, 每行两个整数代表询问的 u,v.
Solution
随机游走问题，貌似跟之前做过的期望不一样。
Code
#include<cstdio>
#include<algorithm>
#define mod 1000000007
#define rep(i,x,y) for(int i=x;i<=y;++i)
using namespace std;
const int N=100010;
struct node{int y,next;
}a[N<<1];
int tot,head[N],n,Q,f[N],g[N],dep[N],ff[N][18],deg[N];
void add(int x,int y){a[++tot]=(node){y,head[x]}; head[x]=tot; deg[x]++;
}
void dfs1(int x,int fa){dep[x]=dep[fa]+1; f[x]=deg[x]; for(int i=head[x];i;i=a[i].next){int y=a[i].y; if (y!=fa){ff[y][0]=x; dfs1(y,x); f[x]+=f[y]; }}return;
}
void dfs2(int x,int fa){for(int i=head[x];i;i=a[i].next){int y=a[i].y; if (y!=fa){g[y]=f[x]-f[y]+g[x]; dfs2(y,x); }}return;
}
void dfs3(int x,int fa){for(int i=head[x];i;i=a[i].next){int y=a[i].y; if (y!=fa){f[y]+=f[x]; g[y]+=g[x]; dfs3(y,x); }}return;
}
inline int lca(int x,int y){if (dep[x]<dep[y]) x^=y^=x^=y; for(int i=17;i>=0;i--) if (dep[x]-(1<<i)>=dep[y]) x=ff[x][i]; if (x==y) return x; for(int i=17;i>=0;i--) if (ff[x][i]!=ff[y][i]) x=ff[x][i],y=ff[y][i]; return ff[x][0];
}
int main(){scanf("%d%d",&n,&Q); rep(i,1,n-1) {int x,y; scanf("%d%d",&x,&y); add(x,y),add(y,x); }dfs1(1,0); dfs2(1,0); f[1]=g[1]=0; dfs3(1,0); rep(j,1,17) rep(i,1,n) ff[i][j]=ff[ff[i][j-1]][j-1]; while(Q--){int x,y,z; scanf("%d%d",&x,&y); z=lca(x,y); printf("%d\n",f[x]-f[z]+g[y]-g[z]); }
}