Time Limits: 2500 ms Memory Limits: 262144 KB
我们首先发现，小B和小C的路径都是以2*Len（b1/c1,b2/c2)的长度为循环节，在某点相遇实质为某时间满足对两个循环节取余的条件。
设B的路径长度为Lb，C的路径长度为Lc，它们公共路径两端点分别为d1,d2
我们首先定义几个概念：
t1.小B进入d1的时间（Mod Lb)
t2.小B进入d2的时间
t3.小C进入d1的时间
t4.小C进入d2的时间
先构出虚树，找到d1,d2
然后分两种情况讨论：
1.小B和小C同向经过公共路径，那么他们最先相遇的点一定是d1/d2
即AnsT需满足两个式子
T=t1(Mod Lb)
T=t2(Mod Lc)
用扩展GCD解决。
2.小B和小C异向经过公共路径。
设d=dis(d1,d2)
首先T须满足：
Lc*q+t4<=T<=Lc*q+t4+d;
Lb*p+t1<=T<=Lb*p+t1+d;
这样保证他们可以同时出现在公共路径上。
但我们还需要讨论奇偶性的情况，因为他们有可能在一条边上“擦肩而过”而不会相遇，
假设他们相遇的时间为T
则
2T=Lc*q+t4+Lb*p+t1+d;
T=(Lc*q+Lb*p+t4+t1+d)/2;
Lc和Lb都是偶数，所以t1,t4,d需满足(t1+t4+d)mod 2=0，这个条件简单判断一下即可
然后要有合法解，需要满足
Max(Lc*q+t4,Lb*p+t1)<=Min(Lc*q+t4+d,Lb*p+t1+d)
经过变换得
Lc*q+t4-t1-d<=Lb*p<=Lc*q+t4-t1+d
可等价于
t4-t1-d<=Lb*p<=t4-t1+d(Mod Lc)
L<=Dx<=R(Mod M)
求出最小的x即可
下面我们要解决L<=Dx<=R(Mod M)这个问题，设G(M,D,L,R)表示这个问题
1.L=0则Ans=0；
2.若(L-1)/gcd(D,M)>=R/gcd(D,M)，显然无解（因为Dx Mod M只能是gcd(D,M)的倍数）
3.若D+D>M则G(M,D,L,R)=G(M,M-D,M-R,M-L)这一步可以保证每次D都至少变为原来的一半，保证O(logN)的复杂度
4.接下来我们要对式子化解
若(L-1)/D<R/D那么存在解，直接返回即可。否则
L<=Dx<=R(Mod M)
-> My+L<=Dx<=My+R
-> L<=Dx-My<=R
-> L%D<=(-M)%D*Y<=R%D (% D)，迭代解决
G(M,D,L,R)=G(D,D-M%D,L%D,R%D)
End.
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<map> using namespace std; typedef long long ll; ll x,y,Lx,Ly; int lb,lc,X,z,n,m,tt,i,b1,b2,c1,c2,j,Mt,tl,ct; int que[200011],fa[200011][19]; int g[200011],next[400011],Y[400011],dep[200011]; bool pc,pz; void star(int i,int j) { tt++; next[tt]=g[i]; g[i]=tt; Y[tt]=j; } ll gcd(ll a,ll b) { if(a%b==0)return b; else return gcd(b,a%b); } ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) return x=1, y=0, a; ll g = exgcd(b, a%b, y, x);; return y -= a/b*x, g; } ll Same(ll A, ll B, ll u, ll v) // Ax+u = By+v { ll x, y, z(v-u), g, ti; g = exgcd(A, B, x, y); if(z%g) return 1e18; x *= z/g, y *= -z/g, A /= g, B /= g; if(x<0) ti = max((-x-1)/B+1, (-y-1)/A+1), x += ti * B, y += ti * A; ti = min(x/B, y/A), x -= ti * B, y += ti * A; return A*g*x + u; } void bfs(int st) { int l,r,x,j,k; l=r=1; que[l]=st; while(l<=r){ x=que[l]; j=g[x]; while(j!=0){ k=Y[j]; if(k!=fa[x][0]){ r++; que[r]=k; fa[k][0]=x; dep[k]=dep[x]+1; } j=next[j]; } l++; } } int getlca(int x,int z) { int i,l,e; if(dep[x]<dep[z])swap(x,z); l=dep[x]-dep[z]; e=0; while(l){ if(l%2==1)x=fa[x][e]; l/=2; e++; } if(x==z)return x; for(i=18;i>=0;i--)if(fa[x][i]!=fa[z][i]){ x=fa[x][i]; z=fa[z][i]; } return fa[x][0]; } int dmax(int a,int b) { if(dep[a]>dep[b])return a; else return b; } int dis(int x,int z) { return dep[x]+dep[z]-2*dep[getlca(x,z)]; } ll G(ll M,ll D,ll L,ll R)//L<=Dx<=R(mod M) { ll t; if((L-1)/D<R/D)return (L-1+D)/D; if(D+D>M)return G(M,M-D,M-R,M-L); t=G(D,D-M%D,L%D,R%D); return (M*t+L-1+D)/D; } ll diff(ll A,ll B,ll u,ll v,ll L)//v-u-d<=Ax<=v-u+d(mod B) { ll l,r,t,s; t=0; l=((v-u-L)%B+B)%B; r=((v-u+L)%B+B)%B; if(l&1)return 1e18; if(B!=L+L&&l<=r&&l){ if((l-1)/gcd(A,B)>=r/gcd(A,B))return 1e18; t=G(B,A%B,l,r); } s=(t*A+u+L-v)/B; return(L+A*t+B*s+u+v)/2; } ll Work(int a,int b,int c,int d) { int u,v,t1,t2,t3,t4,c1,c2,La,Lb,D; ll ans; u=getlca(a,b);v=getlca(c,d); if(dep[u]>dep[v])swap(u,v),swap(a,c),swap(b,d); if(getlca(u,v)!=u)return -1; c1=dmax(getlca(a,c),getlca(a,d)); c2=dmax(getlca(b,c),getlca(b,d)); if(max(dep[c1],dep[c2])<dep[v])return -1; c1=dmax(c1,v);c2=dmax(c2,v); La=2*dis(a,b);Lb=2*dis(c,d); t1=dis(a,c1);t2=dis(a,c2); t3=dis(c,c1);t4=dis(c,c2); D=dis(c1,c2); if(t1>t2)t1=La-t1; else t2=La-t2; if(t3>t4)t3=Lb-t3; else t4=Lb-t4; ans=1e18; ans=min(Same(La,Lb,t1,t3),Same(La,Lb,t2,t4)); ans=min(ans,min(diff(La,Lb,t1,t4,D),diff(La,Lb,t2,t3,D))); if(ans==1e18)ans=-1; return ans; } int main() { pc=true; scanf("%d",&n); for(i=1;i<n;i++){ scanf("%d%d",&X,&z); star(X,z); star(z,X); } bfs(1); for(i=1;i<=18;i++) for(j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1]; scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d%d%d",&b1,&b2,&c1,&c2); printf("%lld ",Work(b1,b2,c1,c2)); } }