題意

給定一棵 \(n\) 個點的樹，有一個棋子初始時在 \(r\) 節點上。Alice 和 Bob 會輪流對棋子進行操作，Alice 先手。

• Alice 操作時，必須把棋子沿著 \(A\) 條兩人都未走過的邊移動。
• Bob 操作時，必須把棋子沿著至多 \(B\) 條邊移動。
• 當 Alice 無法操作時，Bob 必須把棋子沿著至多 \(B\) 條兩人都未走過的邊移動。游戲結束。

Alice 希望最大化最終棋子所在的節點編號，Bob 則希望最小化最終棋子所在的節點編號。求當兩人都以最佳策略行動時，最終棋子所在的節點編號。\(1\leq n\leq 3\times 10^5\)。

題解

非常牛的題啊，被放到了 NOIP 模擬賽 T4。

先判掉 \(A\leq B\) 的情況。此時每輪操作 Bob 都可以往節點 \(1\) 走 \(B-A\) 步，因此答案顯然可以取到 \(1\)。

接下來我們有 \(A>B\)。

很容易想到的一步是，我們二分答案 \(mid\)，把樹上編號 \(\geq mid\) 的點設為 \(1\)，\(<mid\) 的點設為 \(0\)，那么 check 就是要判斷 Alice 是否能走到 \(1\) 點。

將 \(r\) 視作整棵樹的根，當 Alice 從點 \(x\) 開始操作時，不難發現 \(r\) 到 \(x\) 的路徑上的邊都已經被走過了，因此 Alice 只會走向 \(x\) 子樹內的點。而由于 \(B<A\)，Bob 操作完后也不會走出 \(sub_x\)。據此考慮樹形 DP。令 \(f_u\) 表示 Alice 從點 \(u\) 開始操作，會走到什么點，\(g_u\) 表示 Bob 從點 \(u\) 開始操作，會走到什么點。

考慮 \(f\) 的轉移，如果 \(u\) 存在 \(A\) 級兒子，容易列出轉移方程：

我們可以預處理出 \(u\) 的所有 \(A\) 級兒子進行轉移。具體來說，我們在 DFS 預處理的過程中存儲 DFS 棧，那么 \(stk_{top-A}\) 就是 \(stk_{top}\) 的 \(A\) 級祖先。由于每個 \(v\) 恰好會被其 \(A\) 級祖先轉移一次，這部分復雜度是 \(\mathcal{O}(n)\) 的。

但是 \(u\) 也可能不存在 \(A\) 級兒子，對應著此時 Alice 無法操作，游戲進入最終階段。那么我們就需要知道 \(sub_u\) 內是否有與 \(u\) 距離 \(\leq B\) 的點 \(v\)，使得 \(v<mid\)。這是簡單的，我們樹形 DP 出 \(mn_u\) 表示 \(sub_u\) 內滿足 \(v<mid\) 的點 \(v\) 的最淺深度，判斷是否有 \(mn_u-dep_u>B\) 即可。\(mn\) 的轉移是顯然的：

這部分同樣是 \(\mathcal{O}(n)\) 的。

考慮 \(g\) 的轉移，第一眼的想法會是取 \(u\) 的 \(B\) 鄰域內所有 \(f\) 值的與。但這是錯誤的！因為若 Bob 在 \(u\) 操作完后來到了 \(v\) 節點處，使得 \(v\) 是 \(u\) 的祖先，那么 Alice 在 \(v\) 節點處操作時就不能走 \(u\) 節點對應的 \(v\) 的兒子所在的子樹了。

這啟發我們再設計一個 DP 數組 \(h\)，令 \(h_u\) 表示 Alice 從 \(fa_u\) 開始操作，不能走向 \(sub_u\)，會走到哪個點。

這樣我們就可以轉移 \(g\) 了。轉移分為兩部分：一部分是 \(u\) 的 \(B\) 鄰域內，不為 \(u\) 的祖先的節點的 \(f\) 值的與，一部分是 \(u\) 到 \(u\) 的 \(B-1\) 級祖先的路徑上 \(h\) 值的與。

但是這樣轉移 \(g\) 時會不會有后效性呢？如果我們直接 DFS 樹形 DP，是會有的。所以對于這題，我們要按節點的深度從大到小的順序 DP，然后把 \(g_u\) 掛在 \(u\) 的 \(A\) 級祖先處更新，這樣由于 \(A>B\)，我們在更新 \(g_u\) 時，其所需要用來轉移的信息都已經處理好了。

再來考慮 \(h\) 的轉移，其實和 \(f\) 是類似的。我們把 \(h_u\) 掛在 \(fa_u\) 處更新。轉移時同樣要考慮此時 Alice 能否操作：

• Alice 能操作：我們遍歷 \(fa_u\) 的 \(A\) 級兒子，對它們的 \(f\) 值求和得到 \(sum\)。這樣扣除 \(sub_u\) 的貢獻時，只需用 \(sum\) 減去 \(sub_u\) 內的 \(f\) 值的和，然后判斷差是否 \(>0\)。這里需要預處理每個點 \(u\) 位于其 \(A\) 級祖先的哪個子樹中，同樣可以通過預處理時的 DFS 棧得到。
• Alice 不能操作：和 \(f\) 類似，我們需要求出 \(sub_{fa_u}\) 內扣除 \(sub_u\) 后深度最淺的滿足 \(g_v=0\) 的點 \(v\)，轉移 \(mn\) 時順便記錄非嚴格次小值即可。

需要注意 Alice 何時不能操作：除了 \(fa_u\) 不存在 \(A\) 級兒子的情況外，還有一種情況 \(fa_u\) 的 \(A\) 級兒子全部位于 \(sub_u\) 內。這也是好判的。

至此，我們得到了 \(\mathcal{O}(n^2\log{n})\) 的解法。

考慮優化，顯然瓶頸在于 \(g\) 的轉移。可以把 \(g_u\) 的轉移拆成兩部分：

• 對不是 \(u\) 祖先的點 \(v\)，求離 \(u\) 最近的使得 \(f_v=0\) 的點 \(v\) 的距離。
• 求 \(u\) 到 \(u\) 的 \(B-1\) 級祖先的路徑上是否存在點 \(v\) 使得 \(h_v=0\)。

直接做看起來沒前途。我們不妨轉換思路，考察每個點 \(v\) 對 \(g_u\) 的影響。

當處理深度為 \(d\) 的點時，我們會更新深度為 \(d+A\) 處的 \(g\) 值，此時 \(g\) 用到的點的深度必然 \(\geq d+A-B\)。于是我們在開始處理第一個深度為 \(d\) 的點時，加入所有深度為 \(d+A-B\) 的點來更新它們的影響。

對于第一種轉移，我們注意到 \(\operatorname{lca}(u,v)\) 必然處于 \(u\) 到 \(u\) 的 \(B-1\) 級祖先的路徑上，因此考慮在 \(\operatorname{lca}\) 處統計貢獻。更具體地，當加入一個節點 \(x\) 時，我們維護出 \(mnf_x\) 表示 \(sub_x\) 內滿足 \(g_v=0\) 的點 \(v\) 的最淺深度，然后嘗試用它來更新 \(x\) 的兄弟節點的對應子樹，也就是此時我們以 \(fa_x\) 作為 \(\operatorname{lca}\) 統計貢獻。我們在 DFS 序上建一顆線段樹，把這些兄弟節點對應的 DFS 序區間對 \(mnf_x-2dep_{fa_x}\) 取 \(\min\) 即可。這樣子在求離點 \(u\) 最近的 \(f_v=0\) 的點的距離時，只需在將段樹上單點查詢得到的值加上 \(dep_u\) 即可得到真實值。注意 \(x\) 的兄弟節點對應的 DFS 序區間可以被拆分成至多 \(2\) 個連續區間。

第二種轉移其實是簡單的。當加入一個節點 \(x\) 時，我們遍歷其所有兒子 \(y\)，若 \(h_y=0\)，我們就把 \(y\) 對應的 DFS 序區間對 \(-\infty\) 取 \(\min\)，使得子樹內的 \(g\) 全部置為 \(0\)。注意這里會有多余的、深度更大的位置的 \(g\) 值被置為 \(0\)，但是由于這些位置的 \(g\) 值我們前面已經計算出來了，所以實際上沒有影響。

于是，轉移 \(g_u\) 時，我們只需將線段樹上單點查詢得到的值加上 \(dep_u\) 后和 \(mnf_u-dep_u\) 取 \(\min\)，判斷其是否 \(>B\) 即可。

線段樹需要支持區間 \(\operatorname{chkmin}\) 和單點查詢，使用標記永久化即可。

于是我們成功把 check 部分的復雜度優化到了 \(\mathcal{O}(n\log{n})\)。總體時間復雜度為 \(\mathcal{O}(n\log^2{n})\)。

代碼

仔細想清楚你要做什么，代碼就不會很難寫了。

這里放出代碼的主要部分，未經刻意卡常即可通過本題。

struct SegTree {
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
	int tg[N << 2];
	inline void clr() { fill(tg + 1, tg + (n << 2) + 1, INF); }
	inline void upd(int p, int l, int r, int x, int y, int v) {
		if (x <= l && y >= r) return chk_min(tg[p], v), void();
		int mid = l + r >> 1;
		if (x <= mid) upd(ls(p), l, mid, x, y, v);
		if (y > mid) upd(rs(p), mid + 1, r, x, y, v);
	}
	inline int query(int p, int l, int r, int x) {
		if (l == r) return tg[p];
		int mid = l + r >> 1;
		return min(tg[p], x <= mid ? query(ls(p), l, mid, x) : query(rs(p), mid + 1, r, x));
	}
#undef ls
#undef rs
} sgt;

inline void dfs_pre(int x) {
	stk[dep[x] = ++top] = x, ldfn[x] = ++stmp;
	if (top > A) son[stk[top - A]].push_back(x), ++cnts[bel[x] = stk[top - A + 1]];
	for (int i = t.head[x]; ~i; i = t.nxt[i]) {
		int y = t.to[i];
		if (y == fa[x]) continue;
		fa[y] = x, dfs_pre(y);
	}
	--top, rdfn[x] = stmp;
}
inline bool check(int mid) {
	fill(sum + 1, sum + n + 1, 0), sgt.clr();
	for (int i = 1, k = 1; i <= n; ++i) {
		int x = p[i];
		if (dep[x] ^ dep[p[i - 1]]) {
			int dd = dep[x] + A - B;
			while (k <= n && dep[p[k]] == dd) {
				int y = p[k], fy = fa[y];
				for (int j = t.head[y]; ~j; j = t.nxt[j]) {
					int s = t.to[j];
					if (s == fy) continue;
					if (!h[s]) sgt.upd(1, 1, n, ldfn[s], rdfn[s], -INF);
				}
				int val = mnf[y] - dep[fy] * 2;
				int l = ldfn[fy] + 1, r = rdfn[fy];
				if (l < ldfn[y]) sgt.upd(1, 1, n, l, ldfn[y] - 1, val);
				if (rdfn[y] < r) sgt.upd(1, 1, n, rdfn[y] + 1, r, val);
				++k;
			}
		}
		mn0[x] = x < mid ? dep[x] : INF;
		int smn = INF;
		for (int j = t.head[x]; ~j; j = t.nxt[j]) {
			int y = t.to[j];
			if (y == fa[x]) continue;
			if (mn0[y] < mn0[x]) smn = mn0[x], mn0[x] = mn0[y];
			else chk_min(smn, mn0[y]);
		}
		if (son[x].empty()) {
			f[x] = mn0[x] - dep[x] > B, mnf[x] = !f[x] ? dep[x] : INF;
			for (int j = t.head[x]; ~j; j = t.nxt[j]) {
				int y = t.to[j];
				if (y == fa[x]) continue;
				int val = mn0[y] == mn0[x] ? smn : mn0[x];
				h[y] = val - dep[x] > B;
				chk_min(mnf[x], mnf[y]);
			}
		} else {
			int cnt = 0;
			for (int y : son[x]) {
				g[y] = min(mnf[y] - dep[y], sgt.query(1, 1, n, ldfn[y]) + dep[y]) > B;
				cnt += g[y], sum[bel[y]] += g[y];
			}
			f[x] = cnt, mnf[x] = !f[x] ? dep[x] : INF;
			for (int j = t.head[x]; ~j; j = t.nxt[j]) {
				int y = t.to[j];
				if (y == fa[x]) continue;
				chk_min(mnf[x], mnf[y]);
				if (cnts[y] < son[x].size()) h[y] = cnt - sum[y];
				else {
					int val = mn0[y] == mn0[x] ? smn : mn0[x];
					h[y] = val - dep[x] > B;
				}
			}
		}
	}
	return f[rt];
}