[ONTAK2010]Peaks
kruskal重构树练手题。
竟然不强制在线？看到离线水过很不爽：
看到“询问从点\(v\)开始只经过困难值小于等于\(x\)的路径”，马上想到kruskal重构树。先把重构树搞出来，可以先用类似NOI2018归程（）的方法处理，然后把叶子节点按dfs序放到序列上，重构树上每个点的子树的叶子节点在序列上是连续的，预处理出每个点的子树在序列上对应的左右端点，问题就变成了静态区间第\(k\)大，直接主席树。
#include#include #include #define R register#define I inline#define B 1000000using namespace std;const int N = 200003, M = 500003;char buf[B], *p1, *p2;I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin), p1 == p2) ? EOF : *p1++; }I int rd() { R int f = 0; R char c = gc(); while (c < 48 || c > 57) c = gc(); while (c > 47 && c < 58) f = f * 10 + (c ^ 48), c = gc(); return f;}int a[N], b[N], f[N], rot[N], dep[N], fa[N][20], son[N][2], val[N], id[N], l[N], r[N], n, tim, T;struct edge { int u, v, w; }g[M];struct segtree { int p, q, s; }e[N << 5];I int operator < (edge x, edge y) { return x.w < y.w; }I int find(int x) { R int r = x, y; while (f[r] ^ r) r = f[r]; while (x ^ r) y = f[x], f[x] = r, x = y; return r;}void dfs(int x) { dep[x] = dep[fa[x][0]] + 1; for (R int i = 1; i < 20; ++i) fa[x][i] = fa[fa[x][i - 1]][i - 1]; if (x <= n) { id[++tim] = x, l[x] = r[x] = tim; return ; } dfs(son[x][0]), dfs(son[x][1]), l[x] = l[son[x][0]], r[x] = r[son[x][1]];}void build(int &k, int l, int r) { k = ++T; if (l == r) return ; R int m = l + r >> 1; build(e[k].p, l, m), build(e[k].q, m + 1, r);}int modify(int k, int l, int r, int x) { R int t = ++T; e[t].p = e[k].p, e[t].q = e[k].q, e[t].s = e[k].s + 1; if (l == r) return t; R int m = l + r >> 1; if (x <= m) e[t].p = modify(e[k].p, l, m, x); else e[t].q = modify(e[k].q, m + 1, r, x); return t;}int query(int k, int t, int l, int r, int x) { if (l == r) return x <= e[t].s - e[k].s ? l : -1; R int m = l + r >> 1, y = e[e[t].q].s - e[e[k].q].s; if (x > y) return query(e[k].p, e[t].p, l, m, x - y); else return query(e[k].q, e[t].q, m + 1, r, x);}int main() { R int S, m, Q, i, x, y, z, cnt; cnt = n = rd(), m = rd(), Q = rd(); for (i = 1; i <= n; ++i) f[i] = i, a[i] = b[i] = rd(); sort(b + 1, b + n + 1), S = unique(b + 1, b + n + 1) - b - 1, build(rot[0], 1, S); for (i = 1; i <= m; ++i) g[i] = (edge){rd(), rd(), rd()}; sort(g + 1, g + m + 1); for (i = 1; i <= m; ++i) { x = find(g[i].u), y = find(g[i].v); if (x ^ y) { val[++cnt] = g[i].w, f[cnt] = f[x] = f[y] = cnt; son[cnt][0] = x, son[cnt][1] = y, fa[x][0] = fa[y][0] = cnt; } } dfs(cnt); for (i = 1; i <= n; ++i) rot[i] = modify(rot[i - 1], 1, S, lower_bound(b + 1, b + S + 1, a[id[i]]) - b); while (Q--) { x = rd(), y = rd(), z = rd(); for (i = 19; ~i; --i) if (dep[x] - (1 << i) > 0 && val[fa[x][i]] <= y) x = fa[x][i]; z = query(rot[l[x] - 1], rot[r[x]], 1, S, z); printf("%d\n", ~z ? b[z] : -1); } return 0;}