原题链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1628
花了一个早上+半个下午终于把这题切掉了……
（膜出题人）
我们考虑斐波那契数列的通项公式：
$$ F(i)=[(\frac{1+\sqrt{5}}{2})^{i}-(\frac{1-\sqrt{5}}{2})^{i}]*\frac{1}{\sqrt{5}} $$
最后的$ \frac{1}{\sqrt{5}} $ 我们可以拿掉，输出时再丢进答案。
然后考虑对前面两项分开单独处理。
设$G(i)=(\frac{1+\sqrt{5}}{2})^{i}$ 那么这时可以发现 $G(a+b)=G(a)*G(b)$ 有了这个性质，我们就可以把东西统计完再乘起来了。
具体来说，先预处理出从一个点向上走$2^{i}$步之后，这条链上的点从下往上走能得到的贡献，从上往下相同，以及该链内部的点两两之间对答案的贡献（其实前面从上往下的统计只是为这部分服务）。
对于每组询问，先求出两点的lca，然后分别统计这两个点到lca的链的答案，再合并起来，合并的过程有很多细节，详见代码。
运气#1（UPD at 2017.4.24：已经被踩辣）
#include<cstdio>
#include<algorithm>
#define MN 100001
using namespace std;
int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
const int S1=,S2=,MOD=1e9+,S3=;
struct na{int y,ne;}b[MN<<];
int n,m,x,y,f[MN][],g[MN][],G[MN][],A[MN][],K[MN][],l[MN],num=,S[][MN],X[MN],Y[MN],Z[MN],s[MN],de[MN],mmh[MN],Lx[MN],Ly[MN],AP[MN];
inline void in(int x,int y){b[++num].y=y;b[num].ne=l[x];l[x]=num;}
inline int M(int x){while (x>=MOD)x-=MOD;while (x<)x+=MOD;return x;}
void DFS(int x){
s[x]=;
register int i;
for (i=;i<=;i++) if (f[f[x][i-]][i-]) f[x][i]=f[f[x][i-]][i-];else break;
for (i=;i<=;i++) if (f[K[x][i-]][i]) K[x][i]=f[K[x][i-]][i];else break;
for (;i;i--) K[x][i]=K[x][i-];K[x][]=x;
for (i=l[x];i;i=b[i].ne)
if (b[i].y!=f[x][]){
de[b[i].y]=de[K[b[i].y][]=f[b[i].y][]=x]+;
DFS(b[i].y);
AP[x]=M(AP[x]+1LL*s[x]*s[b[i].y]%MOD);
s[x]+=s[b[i].y];
}
}
inline int lca(int x,int y,int &a,int &b){
for (register int i=;i>=;i--)
if (de[f[x][i]]>=de[y]) x=f[x][i];
if (x==y) return x;
for (register int i=;i>=;i--)
if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
a=x;b=y;
return f[x][];
}
void dfs(int x,int o){
A[x][]=1LL*AP[x]*S[o][]%MOD;
g[x][]=G[x][]=1LL*s[x]*S[o][]%MOD;
for (register int i=;i<=;i++)
if (K[x][i])
g[x][i]=M((1LL*(g[x][i-]-s[K[x][i-]])*S[o][<<(i-)]+g[f[x][i-]][i-])%MOD),
G[x][i]=M((1LL*(G[f[x][i-]][i-]-g[K[x][i-]][])*S[o][<<(i-)]+G[x][i-])%MOD),
A[x][i]=M((1LL*g[x][i-]*(G[f[x][i-]][i-]-g[K[x][i-]][])+A[x][i-]+A[f[x][i-]][i-]-1LL*s[K[x][i-]]*M(G[f[x][i-]][i-]-g[K[x][i-]][]))%MOD);
for (register int i=l[x];i;i=b[i].ne)
if (b[i].y!=f[x][]) dfs(b[i].y,o);
}
inline void work(int x,int z,int &_A,int &_g,int o){
int p=;_A=;_g=;
for (register int i=;i>=;i--)
if (de[K[x][i]]>=de[z]){
_A=M((1LL*_g*(G[x][i]-g[p][])+_A+A[x][i]-1LL*s[p]*M(G[x][i]-g[p][]))%MOD);
_g=M((1LL*(_g-s[p])*S[o][<<i]+g[x][i])%MOD);
if (K[x][i]==z) return;
p=K[x][i];
x=f[x][i];
}
}
inline void calc(int x){
int Ax,Ay,gx,gy;
register int i;
dfs(,x);
for (i=;i<=m;i++)
if (Y[i]==Z[i]){
work(X[i],Z[i],Ax,gx,x);
mmh[i]=M(mmh[i]+(x?-1LL:1LL)*(1LL*gx*(n-s[Z[i]])+Ax)%MOD);
}else{
work(X[i],Lx[i],Ax,gx,x);work(Y[i],Ly[i],Ay,gy,x);
mmh[i]=M(mmh[i]+(x?-1LL:1LL)*(1LL*(gx+gy)*(n-s[Lx[i]]-s[Ly[i]])%MOD*S[x][]+1LL*gx*gy%MOD*S[x][]+Ax+Ay+A[Z[i]][]-(1LL*s[Lx[i]]*(s[Z[i]]-s[Lx[i]])+1LL*s[Ly[i]]*(s[Z[i]]-s[Lx[i]]-s[Ly[i]]))%MOD*S[x][]+(1LL*(s[Z[i]]-s[Lx[i]]-s[Ly[i]])*(n-s[Z[i]]))%MOD*S[x][])%MOD);
}
}
int main(){
register int i;
n=read();
for (i=;i<n;i++) x=read(),y=read(),in(x,y),in(y,x);
S[][]=S[][]=;
for (i=;i<=n;i++) S[][i]=1LL*S[][i-]*S1%MOD,S[][i]=1LL*S[][i-]*S2%MOD;
de[]=;DFS();
m=read();
for (i=;i<=m;i++){
X[i]=read();Y[i]=read();
if (de[X[i]]<de[Y[i]]) swap(X[i],Y[i]);
Z[i]=lca(X[i],Y[i],Lx[i],Ly[i]);
}
calc();calc();
for (i=;i<=m;i++) printf("%d\n",1LL*mmh[i]*S3%MOD);
}