LOJ 6192. 「美团 CodeM 复赛」城市网络

tony102

2021 年 07 月 29 日

1252 次浏览

暂无评论

560字数

题解

[Link](https://loj.ac/p/6192)

## Sol

本来是想看看可持久化栈的,可是觉得倍增的做法又简洁又好实现.

非常暴力, 首先预处理往上跳 $2^i$ 步的祖先和这条链上的最大 $a_i$ 的两个数组, $f_{i,j}$ 和 $mx_{i,j}$

现在我们是要往上跳的过程中在比当前 $c$ 价值严格大于的珠宝. 那么可以每次往上跳一段 $a_i$ 都比 $c$ 小的, 然后在这个比 $c$ 大的位置上买入. 那么我们可以再倍增处理一个数组 $g_{i,j}$ 表示 $i$ 号点往上跳 $2^j$ 幂步第一个比 $c$ 大的位置的编号. 这样每次往上跳先跳到第一个比 $c$ 大的位置以后, 在 $g$ 上跳就可以了.

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 1e5 + 5;

int n, q, num;
int head[SIZE], a[SIZE], dep[SIZE], f[SIZE][21], g[SIZE][21], mx[SIZE][21];

struct node {
	int to, nxt;
} edge[SIZE << 1];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs(int u, int fa) {
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == fa) continue;
		f[v][0] = u, dep[v] = dep[u] + 1, mx[v][0] = a[v];
		for (int j = 1; j <= 20; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
		dfs(v, u);
	}
}

int main() {
	n = read(), q = read();
	for (int i = 1; i <= n; ++ i) a[i] = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v), addEdge(v, u);
	}
	dep[1] = 1, mx[1][0] = a[1]; dfs(1, 0);
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= 20; ++ j) mx[i][j] = std::max(mx[i][j - 1], mx[f[i][j - 1]][j - 1]);
	}
	for (int i = 1; i <= n; ++ i) {
		int u = i;
		for (int j = 20; ~j; -- j) {
			if (mx[u][j] <= a[i]) u = f[u][j];
		}
		g[i][0] = u;
	}
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= 20; ++ j) g[i][j] = g[g[i][j - 1]][j - 1];
	}
	while (q --) {
		int u = read(), v = read(), c = read(), ans = 0;
		for (int i = 20; ~i; -- i) {
			if (dep[f[u][i]] >= dep[v] && mx[u][i] <= c) u = f[u][i];
		}
		ans = a[u] > c;
		for (int i = 20; ~i; -- i) {
			if (dep[g[u][i]] >= dep[v]) ans += 1 << i, u = g[u][i];
		}
		printf("%d\n", ans);
	}
	return 0;
}
```

最后修改：2021 年 09 月 04 日