作法：
這題我的作法是按照官方解的作法寫的，這裡大概提一些官方解裡比較沒有寫到的東西，還有我的實作方法。
首先是求出兩條路徑的共同部份（對了，我的記號是記兩條路徑分別是$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$的邊，這樣不會影響到我們要求的任何東西。有了這件事之後，可以發現給定的這四個點形成的圖形只會有以下兩種：
再來則是轉換後的數論問題，第一部份是要能夠求出以下問題的答案：給定$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) ; } }
沒有留言:
張貼留言