solution
首先求出两条路径 \((A,B)\) \((C,D)\) 的交路径，记作 \((S,T)\) 。
那么假设相遇在某个节点 \(u\)，相遇的条件可以写成下面的式子：
其中: \(t_1,t_2\) 为周期，\(r_1,r_2\) 为调整参量，\(d_1,d_2\) 为方向向量， \(s\) 为 \(u\) 到 \(S\) 的距离。
- 当 \(d_1=d_2\) 时
等价于 \(k_1t_1+r_1=k_2t_2+r_2\) ，我们用 \(exgcd\) 随便做 。
- 当 \(d_1\neq d_2\) 时
等价于 \(k_1t_1+r_1=k_2t_2+r_2+2s\)
因为 \(t_1,t_2\) 都是偶数，所以 \(r_1-r_2\) 必定是偶数，因此我们整体除掉 \(2\) ，得到：
\(k_1t_1'-k_2t_2'+r'=s(0\leq s < dis(S,T))\) 。
因为 \(t_2'\geq dis(S,T)\) ，所以 \(k_1t_1'+r'\equiv s'(\bmod t_2')\) ，即为 \((k_1t_1+r')\bmod t_2'<dis(S,T)\)
考虑一个更加一般的问题：
求 \(Ax(\bmod B)\in [L,R]\) 的最小正整数 \(x\) 。
因为 $Ax(\bmod B)=Ax- B\lfloor \frac{Ax}{B} \rfloor $，设 \(B=pA+q,t=\lfloor \frac{Ax}{B}\rfloor\)，那么 \(Ax(\bmod B)=Ax-(pA+q)t=A(x-pt)-qt\) 。
如果 \(\lfloor \frac{L-1}{A}\rfloor \neq \lfloor \frac{R}{A}\rfloor\)，那么显然就是 \(x=\lceil \frac{L}{A}\rceil\) 。
否则，\(L,R\) 属于同一个剩余系，一定就满足 \(L\bmod A\leq R\bmod A\) 。可以把整个式子对 \(A\) 取模，是不影响的。
也就是 \(-qt\in [L\bmod A,R\bmod A]\)，也就是 \(qt\in [-R\bmod A,-L \bmod A]\) ，我们递归计算 \(t\) 即可。
复杂度同类欧几里得算法，\(O(\log n)\) 。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
typedef long long LL;
struct edge
{
int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
e[++t].y=y;
e[t].next=link[x];
link[x]=t;
}
int n,m;
int dep[N],f[N][20];
void dfs(int x,int pre)
{
dep[x]=dep[pre]+1;
f[x][0]=pre;
for(int k=1;f[x][k-1];k++)f[x][k]=f[f[x][k-1]][k-1];
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==pre)continue;
dfs(y,x);
}
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int k=19;k>=0;k--)if(dep[f[x][k]]>=dep[y])x=f[x][k];
if(x==y) return x;
for(int k=19;k>=0;k--)if(f[x][k]!=f[y][k])
{
x=f[x][k];
y=f[y][k];
}
return f[x][0];
}
inline int dis(int x,int y)
{
return dep[x]+dep[y]-2*dep[lca(x,y)];
}
const LL INF = 1e18;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
if(!b)
{
x=1;y=0;
return a;
}
LL d=exgcd(b,a%b,x,y);
LL z=x;x=y;y=z-(a/b)*y;
return d;
}
LL get(LL A,LL B,LL C)//Ax=B(mod C) Ax+Cy=B
{
A=(A%C+C)%C;
B=(B%C+C)%C;
if(A==0)
{
if(B==0) return 0;
return INF;
}
LL x,y;
LL d=exgcd(A,C,x,y);
if(B%d!=0) return INF;
LL mod=C/d;
return (x*(B/d)%mod+mod)%mod;
}
LL Exclid(LL A,LL B,LL L,LL R)//Ax(mod B)\in [L,R]
{
A%=B;
//printf("Ex(%lld %lld %lld %lld\n",A,B,L,R);
if(L>R) return INF;
if(A==0)
{
if(L<=0&&0<=R) return 0;
return INF;
}
if(L==0)return 0;
if((L-1)/A!=R/A) return (L-1)/A+1;
LL t=Exclid(B%A,A,(A-R%A)%A,(A-L%A)%A);
if(t==INF) return INF;
return (t*B+L+A-1)/A;
}
int Max(int x,int y)
{
return dep[x]>dep[y]?x:y;
}
bool cmp(int x,int y)
{
return dep[x]>dep[y];
}
LL o[4];
LL solve1(LL T1,LL r1,LL T2,LL r2)
{
//printf("solve1(%lld %lld %lld %lld)\n",T1,r1,T2,r2);
LL x=get(T1,r2-r1,T2);
if(x==INF)return INF;
return x*T1+r1;
}
LL solve2(LL T1,LL r1,LL T2,LL r2,LL L)
{
//cout<<T1<<' '<<r1<<' '<<T2<<' '<<r2<<' '<<L<<endl;
LL ans=INF;
ans=min(ans,solve1(T1,r1,T2,r2+2*L)-L);
if((r2-r1)%2!=0)return INF;
LL t1=T1/2,t2=T2/2,r=(r1-r2)/2;r=(r%t2+t2)%t2;
//cout<<t1<<' '<<t2<<' '<<L<<' '<<r<<endl;
LL x=Exclid(t1,t2,0,L-1-r);
//cout<<x<<endl;
if(x!=INF)ans=min(ans,T1*x+r1-(t1*x+r)%t2);
x=Exclid(t1,t2,t2-r,min(L-1+t2-r,t2-1));
if(x!=INF)ans=min(ans,T1*x+r1-(t1*x+r)%t2);
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,0);
cin>>m;
while(m--)
{
int A,B,C,D;
scanf("%d %d %d %d",&A,&B,&C,&D);
o[0]=lca(A,C);o[1]=lca(A,D);o[2]=lca(B,C);o[3]=lca(B,D);
int E=lca(A,B),F=lca(C,D);
sort(o,o+4,cmp);
int P=o[0],Q=o[1];
if(P==Q&&dep[P]<max(dep[E],dep[F])) printf("-1\n");
else
{
//chase
LL T1,T2,r1,r2,d1,d2;
LL ans=INF;
T1=2*dis(A,B);T2=2*dis(C,D);
//P->Q,P->Q
if(dis(A,P)<=dis(A,Q))r1=dis(A,P);else r1=dis(A,B)+dis(P,B);
if(dis(C,P)<=dis(C,Q))r2=dis(C,P);else r2=dis(C,D)+dis(P,D);
ans=min(ans,solve1(T1,r1,T2,r2));
//Q->P,P->Q
if(dis(A,P)<=dis(A,Q))r1=dis(A,B)+dis(B,P);else r1=dis(A,P);
ans=min(ans,solve2(T1,r1,T2,r2,dis(P,Q)));
swap(P,Q);
if(dis(A,P)<dis(A,Q))r1=dis(A,P);else r1=dis(A,B)+dis(P,B);
if(dis(C,P)<dis(C,Q))r2=dis(C,P);else r2=dis(C,D)+dis(P,D);
ans=min(ans,solve1(T1,r1,T2,r2));
//Q->P,P->Q
//cout<<P<<' '<<Q<<endl;
if(dis(A,P)<dis(A,Q))r1=dis(A,B)+dis(B,P);else r1=dis(A,P);
ans=min(ans,solve2(T1,r1,T2,r2,dis(P,Q)));
if(ans>=1e16)printf("-1\n");
else printf("%lld\n",ans);
}
}
return 0;
}