題目

傳送門 to usOJ

題目概要
有兩棵樹，有兩顆棋子分別在這兩顆樹上面，在第 2 k + i ( i ∈ { 0 , 1 } ) 2k+i(i\in\{0,1\}) 2k+i(i∈{0,1}) 輪中，你可以移動第 i + 1 i+1 i+1 棵樹上的棋子至一個相鄰節點，或者不移動，結束狀態是兩顆棋子都在各自的樹的根節點 1 1 1 上，該游戲的得分為任意時刻兩個棋子所在的節點的編號和的 max ? \max max ，最小化得分，

資料范圍與提示
∑ n ≤ 1 0 6 \sum n\le 10^6 ∑n≤106 且資料組數 T ≤ 1 0 4 T\le 10^4 T≤104 ，

思路

把一個棋子的連續移動（也就是說，這一段時間內另一顆棋子不動）叫做 “一輪” ，

你可以大膽猜結論，一輪中一定是編號大的移動到編號小的，然后你用 i n d u c t i o n \tt induction induction 來證明，只有一輪的時候顯然正確，因為 1 1 1 是編號最小的，當第一輪是小編號到大編號，剩下的步驟都是大到小（歸納法）時，取消第一輪，將其放到第二輪中去，你畫個圖就能很容易說明，

{ a → b → c → d → e ( a < c ∧ c > e ) x → y → z ( x > z ) \begin{cases} a→b→c→d→e\quad(a<c\wedge c>e)\\ x→y→z\quad(x>z) \end{cases} {a→b→c→d→e(a<c∧c>e)x→y→z(x>z)?

這里用 a , c , e a,c,e a,c,e 表示三個歇腳點，滿足第一輪 a → c a→c a→c 是小到大，而另一顆樹中的歇腳點是 x , z x,z x,z ，中間的 b b b 表示路徑上的最大值，也就是 b = max ? v ∈ p a t h ( a , c ) v b=\max_{v\in path(a,c)}v b=maxv∈path(a,c)?v ，而 d , y d,y d,y 同理， b b b 可以為 a a a 或 c c c ，

容易發現這里的代價是 ? b , x ? , ? c , y ? , ? d , z ? ?b,x?,?c,y?,?d,z? ?b,x?,?c,y?,?d,z?

（這里 ? p , q ? \lang p,q\rang ?p,q? 表示 a n s ≥ p + q ans\ge p+q ans≥p+q ，也就是題目中所說的編號和），

此時考慮另一個策略，第一輪就是 x → z x\rightarrow z x→z ，而第二輪為 a → e a\rightarrow e a→e ，此時的代價是

? a , y ? , ? b , z ? , ? d , z ? ?a,y?,?b,z?,?d,z? ?a,y?,?b,z?,?d,z?

仔細比對一下， ? b , x ? ?b,x? ?b,x? 劣于 ? b , z ? ?b,z? ?b,z? 且 ? c , y ? ?c,y? ?c,y? 劣于 ? a , y ? ?a,y? ?a,y? ，所以更改后更優，所以結論成立，

知道了結論，不如二分一個答案，那么每個點可達的位置就是一個 不斷變大的連通塊，然后兩個點都不斷走到一個編號較小的點即可，如果兩邊都走不動就完蛋了，

我以為 b f s \tt bfs bfs 可行，不曾想，需要走到編號最小的點，所以要用優先佇列，所以是 O ( n log ? 2 n ) \mathcal O(n\log^2n) O(nlog2n) ，毫無疑問可能被卡掉，

考慮一下兩個優化：第一，編號的范圍很小，讓人聯想到 桶排，第二，答案的范圍很小，我們去掉二分，只在兩邊都走不動時增大猜測的答案，結果就直接變成線性的了！ O ( n ) \mathcal O(n) O(n) 即可解決，

代碼

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long int_;
inline int readint(){
	int a = 0; char c = getchar(), f = 1;
	for(; c<'0'||c>'9'; c=getchar())
		if(c == '-') f = -f;
	for(; '0'<=c&&c<='9'; c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MaxN = 2000005;

struct Edge{
	int to, nxt; Edge(){ }
	Edge(int T,int N):to(T),nxt(N){}
};
Edge e[MaxN<<1];
int head[MaxN], cntEdge;
void addEdge(int a,int b){
	e[cntEdge] = Edge(b,head[a]);
	head[a] = cntEdge ++;
}

bool vis[MaxN]; // 還有一步可到達
int now[2]; // 目前走到的 min id
int sy[2]; // 正在考慮走到哪個地方
inline void dfs(int d,int x){
	now[d] = min(now[d],x);
	for(int i=head[x]; ~i; i=e[i].nxt){
		if(vis[e[i].to]) continue;
		vis[e[i].to] = true;
		if(e[i].to <= sy[d])
			dfs(d,e[i].to); // 立即遞回
	}
}
int main(){
	for(int T=readint(); T; --T){
		int n = readint(); cntEdge = 0;
		for(int i=1; i<=(n<<1); ++i)
			head[i] = -1, vis[i] = 0;
		for(int i=1,a,b; i<n; ++i){
			a = readint(), b = readint();
			addEdge(a,b), addEdge(b,a);
		}
		for(int i=1,a,b; i<n; ++i){
			a = readint()+n, b = readint();
			addEdge(a,b+n), addEdge(b+n,a);
		}
		sy[0] = now[0] = readint();
		sy[1] = now[1] = readint()+n;
		int w = now[0]+now[1]; // 最小答案
		vis[sy[0]] = vis[sy[1]] = true;
		for(int d=0; now[0]+now[1]!=n+2; d^=1){
			if(now[d] == 1+d*n) continue; // 已處理
			while(!vis[sy[d]]) ++ sy[d]; // 桶排
			if(sy[d]+now[d^1] > w)
				++ w; // 卡住了，必須調大 w
			while(sy[d]+now[d^1] <= w){
				now[d] = min(now[d],sy[d]);
				for(int i=head[sy[d]]; ~i; i=e[i].nxt){
					if(vis[e[i].to]) continue;
					vis[e[i].to] = true;
					if(e[i].to <= sy[d]) // 已考慮過
						dfs(d,e[i].to);
				}
				++ sy[d]; // 考慮下一個 id
				if(now[d] == 1+d*n) break;
				while(!vis[sy[d]]) ++ sy[d];
			}
		}
		printf("%d\n",w-n);
	}
	return 0;
}