NOI2021 統一省選（A卷） Day2 T1 寶石（樹上主席樹+二分+倍增）

NOI2021 統一省選（A卷） Day2 T1 寶石

題目大意

• 大小為 n n n的樹上，每個點有一個權值 w i ≤ [ 1 , m ] w_i\le[1,m] wi​≤[1,m]，給出一個無重序列 P P P， q q q組詢問，每次求從 x x x到 y y y的最短路徑的點權能從 1 1 1開始對應序列 P P P的多少位。
• n , q ≤ 2 ∗ 1 0 5 ， m , ∣ P ∣ ≤ 5 ∗ 1 0 4 n,q\le2*10^5，m,|P|\le5*10^4 n,q≤2∗105，m,∣P∣≤5∗104

題解

• 有一檔 m ≤ 300 m\le300 m≤300的部分分，可以直接記錄每個點向上權值為 i i i的點是哪個，然後從起點貪心向上跳，從終點二分後貪心向上跳，時間複雜度 O ( q m log ⁡ 2 m ) O(qm\log_2 m) O(qmlog2​m)，比賽時被卡了沒拿到這檔分。
• 但由此可以想到更快的做法，首先當 m m m特别大時不能用數組直接記錄，因為是在樹上且每次由父親轉移來并修改，是以可以用樹上主席樹記錄。
• 同時，二分後也不能一個一個暴力跳，直接考慮倍增。使用兩個倍增數組分别記錄從每個點開始按 P P P序列中目前點權值位置開始正着和反着跳 2 i 2^i 2i到達的點，需要先在主席樹中查詢出起點向上的第一個 P 1 P_1 P1​和終點向上第一個 P m i d P_{mid} Pmid​的位置。
• 時間複雜度 O ( q log ⁡ 2 2 m ) O(q\log^2_2m) O(qlog22​m)，理論可過，實際常數較大，視評測環境而定（事實跑的極慢）。

代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 200010
#define M 50010
int n, m, C, P[M], pr[M], a[N];
int last[N], nxt[N * 2], to[N * 2], len = 0;
int tot = 0, h[N], dp[N];
int F[N][16], G[N][16], H[N][18];
struct {
	int l = 0, r = 0, x;
}f[N * 20];
void add(int x, int y) {
	to[++len] = y;
	nxt[len] = last[x];
	last[x] = len;
}
int find(int v, int l, int r, int x) {
	if(l == r) return f[v].x;
	int mid = (l + r) / 2;
	if(x <= mid) {
		if(f[v].l) return find(f[v].l, l, mid, x);
	}
	else {
		if(f[v].r) return find(f[v].r, mid + 1, r, x);
	}
	return 0;
}
void ins(int v, int v0, int l, int r, int x, int c) {
	if(l == r) f[v].x = c;
	else {
		int mid = (l + r) / 2;
		if(x <= mid) {
			if(!f[v].l) f[v].l = ++tot;
			ins(f[v].l, f[v0].l, l, mid, x, c);
			f[v].r = f[v0].r;
		}
		else {
			if(!f[v].r) f[v].r = ++tot;
			ins(f[v].r, f[v0].r, mid + 1, r, x, c);
			f[v].l = f[v0].l;
		}
	}
}
void dfs(int k, int fa) {
	h[k] = ++tot;
	ins(h[k], h[fa], 1, m, a[k], k);
	
	if(pr[a[k]] != C) F[k][0] = find(h[k], 1, m, P[pr[a[k]] + 1]);
	for(int i = 1; i < 16 && F[k][i - 1]; i++) F[k][i] = F[F[k][i - 1]][i - 1];
	if(pr[a[k]] != 1) G[k][0] = find(h[k], 1, m, P[pr[a[k]] - 1]);
	for(int i = 1; i < 16 && G[k][i - 1]; i++) G[k][i] = G[G[k][i - 1]][i - 1];
	H[k][0] = fa;
	for(int i = 1; i < 18 && H[k][i - 1]; i++) H[k][i] = H[H[k][i - 1]][i - 1];
	
	dp[k] = dp[fa] + 1;
	
	for(int i = last[k]; i; i = nxt[i]) if(to[i] != fa) dfs(to[i], k);
	
}
int lca(int x, int y) {
	if(dp[x] < dp[y]) swap(x, y);
	for(int i = 17; i >= 0; i--) if(dp[x] - (1 << i) >= dp[y]) x = H[x][i];
	if(x == y) return x;
	for(int i = 17; i >= 0; i--) if(H[x][i] != H[y][i]) x = H[x][i], y = H[y][i];
	return H[x][0];
}
int read() {
	int s = 0;
	char x = getchar();
	while(x < '0' || x > '9') x = getchar();
	while(x >= '0' && x <= '9') s = s * 10 + x - 48, x = getchar();
	return s;
}
int main() {
	int i, x, y;
	n = read(), m = read(), C = read();
	for(i = 1; i <= C; i++) P[i] = read(), pr[P[i]] = i;
	for(i = 1; i <= n; i++) a[i] = read();
	for(i = 1; i < n; i++) {
		x = read(), y = read();
		add(x, y), add(y, x);
	}
	dfs(1, 0);
	int Q = read();
	while(Q--) {
		x = read(), y = read();
		int L = lca(x, y), t;
		x = find(h[x], 1, m, P[1]);
		if(dp[x] < dp[L]) t = 0;
		else {
			t = 1;
			for(i = 15; i >= 0 && dp[x] >= dp[L]; i--) {
				if(dp[F[x][i]] >= dp[L]) x = F[x][i], t += 1 << i;
			}	
		}
		int l = t, r = C, ans = t, y0 = y;
		while(l <= r) {
			int mid = (l + r) / 2, s;
			y = find(h[y0], 1, m, P[mid]);
			if(dp[y] < dp[L]) s = mid + 1;
			else {
				s = mid;
				for(i = 15; i >= 0 && dp[y] >= dp[L]; i--) {
					if(dp[G[y][i]] >= dp[L]) y = G[y][i], s -= 1 << i;
				}
			}
			if(s <= t + 1) ans = mid, l = mid + 1; else r = mid - 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}
           

自我小結

• 感覺這題全省排名靠前的都切穿了，要是切了直接全省前十。
• 其實我把部分分都寫完了，但是有25分好像帶個log被卡了，還有20分官方資料出大鍋？！
• 這題這種解法和我的部分分其實很像的，最近樹上主席樹寫的少了沒有意識到，要是寫了就算被卡常分數也不至于現在這麼慘。