Tony102's Blog - 树上倍增
type: channel
link: https://tony102.com/index.php/tag/%E6%A0%91%E4%B8%8A%E5%80%8D%E5%A2%9E/
items: LOJ 6192. 「美团 CodeM 复赛」城市网络

LOJ 6192. 「美团 CodeM 复赛」城市网络
type: item
date: 2021-07-29T21:07:00+08:00
description: LinkSol本来是想看看可持久化栈的,可是觉得倍增的做法又简洁又好实现.非常暴力, 首先预处理往上跳 $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#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]] >= …