[CF 500G] New Year Running

作法：

這題我的作法是按照官方解的作法寫的，這裡大概提一些官方解裡比較沒有寫到的東西，還有我的實作方法。

首先是求出兩條路徑的共同部份（對了，我的記號是記兩條路徑分別是$u_1$~$v_1$和$u_2$~$v_2$），還有之後需要用到的重要的數字$f_1,f_2,t_1,t_2,t_3,t_4,dis$，其中$f_1,f_2$分別代表兩條路徑的兩倍長，$dis$則代表兩條路徑共同部份的長度，$t_1,t_2,t_3,t_4$則和題解中的定義一樣。這裡先假設在$u_1,v_1,u_2,v_2$中沒有任何一點是另一點的祖先，這種情形的算法可以直接套到一般情形上。至於為什麼我目前也不是很清楚，不過大概可以想成：如果$X$是$Y$的祖先，那麼可以把$X$替換成另一個虛擬節點$Z$，然後把$X$接到$Z$底下，並且在他們之間連一條長度為$0$的邊，這樣不會影響到我們要求的任何東西。有了這件事之後，可以發現給定的這四個點形成的圖形只會有以下兩種：

其中黑點代表給定的四個點，白點則是某兩點的LCA。雖然他們都長的像這兩種情形，不過他們對應到的黑色節點們會有很多種不同的排列方式。可以算出如果四個點的位置亂排的話，左邊有$12$種，右邊則有$3$種，並且不符合條件（也就是路徑沒有重合的部份）的排列左邊有$4$種，右邊有$1$種。因此總共有$10$種情形，我沒有想到比較好的作法，所以很白癡的都討論了一遍......具體的方法是，如果這四點是形成左邊這張圖的話，那麼一定存在一個點$X$，使得$X$和另外三點的LCA都一樣，也就是這時候我們就知道$X$就是左邊這張圖的左上角那個黑點。而去掉他之後，剩下的圖形也可以用類似的方法來判斷，也就是此時存在一個$Y$，使得他和另外兩點的LCA一樣（此時已排除剛剛找到的$X$），而他就會是圖中上面數來第二個黑點。至於右邊這種情況，注意到左邊兩黑點的LCA和右邊兩黑點的LCA是兄弟的關係，也就是互不為對方的祖先，所以就可以用這件事來判斷當前是否為這種情形。當確定此時是哪種情形的時候所有需要的值就都知道了，只是寫起來很麻煩而已......

再來則是轉換後的數論問題，第一部份是要能夠求出以下問題的答案：給定$a,b,c,d\geq 0$，求出在所有滿足$ax+b=cy+d$的整數$(x,y)$中，當$ax+b$為最小的非負值的時候其值是多少。移項變成$ax-cy=d-b$，因此可以直接套用擴展歐幾里得算法求出一組$(x,y)$的解，再把他調整成讓$ax+b$值最小的解。而在調整的時候如果是用慢慢加的會TLE，要算好要加幾倍再一次加上去才可以，看code應該比較好理解。

再來則是第二部份，也就是求$g$函數的值的部份，我覺得他寫的怪怪的所以自己弄了一個作法。這裡我的記號和他不太一樣，$g(a,b,y,M)$會回傳最小的非負整數$x$，使得$a\leq (x\cdot y)\mod M\leq b$，並且$a,b$滿足$0\leq a\leq b<M$。想像$x$從$0$開始慢慢往上加，那麼$x\cdot y$就會一直$+y$，當他加到$\geq a$的時候，如果他的值$\leq b$，那麼顯然此時的$x$就是最小的解了，直接回傳就可以了，也就是第一步是先確認$\geq a$的最小的$y$的倍數是否可行，如果可以的話就直接回傳。如果不行的話，那麼就代表$a$和$b$之間沒有任何$y$的倍數（包含$a,b$），這件事等一下會用到。那麼此時引入另一個變數$r$，把方程式改寫成$a\leq x\cdot y-M\cdot r\leq b$，也就是我們要求滿足上式的二元組$(x,r)$中，$x$的最小值是多少（當然$r$也要$\geq 0$）。而可以看出$r$越小$x$就越小，所以其實也可以先找出$r$的最小值再推出所求的值。再把這條式子反過來變成$-b\leq r\cdot M-x\cdot y\leq -a$，這時候因為$a,b$之間沒有$y$的倍數，所以可以把這條式子直接模$y$，把最左邊和最右邊都變成介於$0$到$y-1$的數字而不會反號（也就是變成$((-b)\% y+y)\% y$）。也就是現在變成了一個新的問題：求最小的$r$使得$A\leq (r\cdot M)\mod y\leq B$，其中$A$和$B$是剛才提到的值。注意到我們可以把$M$改成$M\% y$，也就是變成了$A\leq (r\cdot (M\% y))\mod y\leq B$，因此這樣就可以遞迴下去處理了，他的過程就和輾轉相除法類似，所以複雜度會是$log$級別的。另外還要注意到，如果此時$M\% y = 0$的話遞迴下去可能會有問題，不過不難發現此時一定無解，所以直接回傳就可以了。

另外在使用這個函式之前還會有些問題。回到官方解中我們要解決的那條式子，此時他形如$yf_2+a\leq xf_1\leq yf_2+b$，要求出最小的非負的$x$是多少。如果直接把$a$和$b$拿去模掉$f_2$然後丟$g$函式的話會有問題，因為有可能$a$和$b$之間有$f_1$的倍數，模下去之後就沒了之類的，因此我們先判斷$x=0$或$y=0$的時候這條式子有沒有解，如果有就直接回傳，沒有的話才用$g$函數來算。

對了，出題者在下面的留言說因為他作過了這題（也就是求$g$函數的值的裸題）所以才會的，可以在傳這題之前用來測測看$g$函數有沒有寫對。

code :

#include<bits/stdc++.h>
#define LL long long
#define INF (1LL<<60)
using namespace std;
const int maxn=200000+10 ;
 
void gcd(LL a,LL b,LL &x,LL &y,LL d)
{
    if(b==0){x=d/a ; y=0 ; return ;}
    gcd(b,a%b,y,x,d) ;
    y-=(a/b)*x ;
}
 
LL cal(LL a,LL b,LL c,LL d) /// a*x+b = c*y+d , return min a*x+b or INF
{
    LL g=__gcd(a,c) ;
    if((b-d)%g) return INF ;
    LL x,y ; gcd(a,-c,x,y,d-b) ;
 
    LL dx=c/g , dy=a/g ;
    if(a*x+b>0)
    {
        LL t=(a*x+b-1)/(a*dx)+1 ;
        x-=t*dx , y-=t*dy ;
    }
    if(a*x+b<0)
    {
        LL t=(-a*x-b-1)/(a*dx)+1 ;
        x+=t*dx , y+=t*dy ;
    }
    return a*x+b ;
}
 
LL solve(LL a,LL b,LL y,LL M) /// find min x s.t. a <= (x*y)%M <= b
{
    if(a==0) return 0 ;
    else if(y*((a-1)/y+1)<=b) return (a-1)/y+1 ;
    else if(M%y==0) return INF ;
    LL r=solve( ((-b)%y+y)%y , ((-a)%y+y)%y , M%y , y ) ;
    return r==INF ? INF : (a+r*M-1)/y+1 ;
}
 
vector<int> v[maxn] ;
int tin[maxn],tout[maxn],tick ;
int d[maxn],anc[18][maxn] ;
void dfs(int x,int f,int dep)
{
    anc[0][x]=f ; d[x]=dep ;
    tin[x]=tick++ ;
    for(int i=1;i<18;i++) anc[i][x]=anc[i-1][anc[i-1][x]] ;
    for(auto i : v[x]) if(i!=f)
        dfs(i,x,dep+1) ;
    tout[x]=tick++ ;
}
 
inline bool isfa(int x,int y) /// x is fa of y
{
    return tin[x]<=tin[y] && tout[x]>=tout[y] ;
}
int LCA(int x,int y)
{
    if(isfa(x,y)) return x ;
    if(isfa(y,x)) return y ;
    for(int i=17;i>=0;i--) if(!isfa(anc[i][x],y))
        x=anc[i][x] ;
    return anc[0][x] ;
}
 
int u1,v1,u2,v2 ;
int f1,f2,dis ;
int t1,t2,t3,t4 ;
bool getpath()
{
    int p1=LCA(u1,v1) , p2=LCA(u2,v2) ;
    int p3=LCA(u1,u2) , p4=LCA(v1,v2) ;
    int p5=LCA(u1,v2) , p6=LCA(u2,v1) ;
    f1=2*(d[u1]+d[v1]-2*d[p1]) ;
    f2=2*(d[u2]+d[v2]-2*d[p2]) ;
    if(p1==p3 && p3==p5) /// u1
    {
        if(p2==p4) /// v2
        {
            dis=d[p6]-d[p2] ;
            t1=d[u1]+d[p2]-2*d[p3] ; t2=f1/2+d[v1]-d[p6] ;
            t3=f2/2+d[v2]-d[p2] ; t4=d[u2]-d[p6] ;
        }
        else if(p2==p6) /// u2
        {
            dis=d[p4]-d[p2] ;
            t1=d[u1]+d[p2]-2*d[p3] ; t2=f1/2+d[v1]-d[p4] ;
            t3=d[u2]-d[p2] ; t4=f2/2+d[v2]-d[p4] ;
        }
        else return 0 ;
    }
    else if(p1==p4 && p4==p6) /// v1
    {
        if(p2==p5) /// v2
        {
            dis=d[p3]-d[p2] ;
            t1=d[u1]-d[p3] ; t2=f1/2+d[p2]+d[v1]-2*d[p1] ;
            t3=d[u2]-d[p3] ; t4=f2/2+d[v2]-d[p2] ;
        }
        else if(p2==p3) /// u2
        {
            dis=d[p5]-d[p3] ;
            t1=d[u1]-d[p5] ; t2=f1/2+d[p3]+d[v1]-2*d[p1] ;
            t3=f2/2+d[v2]-d[p5] ; t4=d[u2]-d[p3] ;
        }
        else return 0 ;
    }
    else if(p2==p3 && p3==p6) /// u2
    {
        if(p1==p4) /// v1
        {
            dis=d[p5]-d[p1] ;
            t1=d[u1]-d[p5] ; t2=f1/2+d[v1]-d[p1] ;
            t3=f2/2+d[v2]-d[p5] ; t4=d[p1]+d[u2]-2*d[p3] ;
        }
        else if(p1==p5) /// u1
        {
            dis=d[p4]-d[p1] ;
            t1=d[u1]-d[p1] ; t2=f1/2+d[v1]-d[p4] ;
            t3=d[p1]+d[u2]-2*d[p3] ; t4=f2/2+d[v2]-d[p4] ;
        }
        else return 0 ;
    }
    else if(p2==p4 && p4==p5) /// v2
    {
        if(p1==p3) /// u1
        {
            dis=d[p6]-d[p3] ;
            t1=d[u1]-d[p3] ; t2=f1/2+d[v1]-d[p6] ;
            t3=f2/2+d[v2]+d[p3]-2*d[p2] ; t4=d[u2]-d[p6] ;
        }
        else if(p1==p6) /// v1
        {
            dis=d[p3]-d[p1] ;
            t1=d[u1]-d[p3] ; t2=f1/2+d[v1]-d[p1] ;
            t3=d[u2]-d[p3] ; t4=f2/2+d[p1]+d[v2]-2*d[p2] ;
        }
        else return 0 ;
    }
    else if(!isfa(p3,p4) && !isfa(p4,p3))
    {
        dis=d[p3]+d[p4]-2*d[p1] ;
        t1=d[u1]-d[p3] ; t2=f1/2+d[v1]-d[p4] ;
        t3=d[u2]-d[p3] ; t4=f2/2+d[v2]-d[p4] ;
    }
    else if(!isfa(p5,p6) && !isfa(p6,p5))
    {
        dis=d[p5]+d[p6]-2*d[p1] ;
        t1=d[u1]-d[p5] ; t2=f1/2+d[v1]-d[p6] ;
        t3=f2/2+d[v2]-d[p5] ; t4=d[u2]-d[p6] ;
    }
    else return 0 ;
    return 1 ;
}
 
void update(LL &ans,int type)
{
    int T1=(type==1 ? t1 : t2) ;
    int T2=(type==1 ? t4 : t3) ;
    if((dis+T1+T2)%2) return ;
    int a=T2-T1-dis , b=T2-T1+dis ; /// y*f2 + a <= x*f1 <= y*f2 + b
 
    int x0=(a-1)/f1+1 , y0=(-b-1)/f2+1 ;
    if(a<=0 && b>=0){ans=min(ans,(LL)(dis+T1+T2)/2) ; return ;}
    if(a>=0 && x0*f1<=b)
        ans=min(ans,(LL)(dis+T1+T2+x0*f1)/2) ;
    else if(a<=0 && y0*f2+a<=0)
        ans=min(ans,(LL)(dis+T1+T2+y0*f2)/2) ;
    else
    {
        LL x=solve((a%f2+f2)%f2,(b%f2+f2)%f2,f1,f2) ;
        LL y=(x*f1-b-1)/f2+1 ;
        if(x!=INF) ans=min(ans,(dis+T1+T2+x*f1+y*f2)/2) ;
    }
}
 
main()
{
    int n ; scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    dfs(1,1,0) ;
    int Q ; scanf("%d",&Q) ;
    while(Q--)
    {
        scanf("%d%d%d%d",&u1,&v1,&u2,&v2) ;
        if(!getpath()){printf("-1\n") ; continue ;}
        LL ans=INF ;
        ans=min(ans,cal(f1,t1,f2,t3)) ;
        ans=min(ans,cal(f1,t2,f2,t4)) ;
        update(ans,1) ;
        update(ans,2) ;
        printf("%I64d\n",ans==INF ? -1 : ans) ;
    }
}