题目传送门(BZOJ/非强制在线)
题目传送门(BZOJ/强制在线)
>原文链接<

题解 :

重构树模板题

Kruskal重构树 :

  • 将Kruskal得到的最小生成树进行重构 :

    对于一条边(u, v)\;val=w, 建立一个代表边的点x, 其权值为w, 并把u, v在当前重构树中的根节点分别连到该点x上, 作为其两个儿子.

    利用并查集维护根节点, 点u的根就是当前的find(u), 在连边的同时, 把u, v的根节点同时并到该点上.

    枚举边的顺序按Kruskal的顺序来

    对于样例来说, 重构树是这样的 :

pic

其中非叶子节点都是由边重构而成的节点

  • 重构树有如下几个性质 :
    1. 二叉树, 大根堆
    2. 原树两点间最大边权, 是这两个点在重构树上LCA的权值
    3. 任意非叶节点, 其子树中两叶节点间最大边权不超过该节点权值(本题需要用到的性质)

由于有了第三个性质, 对于一查询节点a,若它的某级祖先p的点权不超过x, 意味着它能到达p子树中任意一个点, 若其超过x, 从a到达子树外的点一定要经过这个点, 故不符合要求. 所以我们只需要倍增找到这个祖先p ,然后在p的子树里查询第K大即可.

对于子树的处理: 我们对叶子节点建立dfs序, 同时只按该dfs序建立主席树,

对于非叶子节点p,令其dfn为遍历到它的时候的cnt , oud为退出它时的cnt, 当查询其子树时, 由于dfn[p]并不真的包含它子树里的点, 也恰好是它子树前的一个叶子节点, 所以我们直接查询Tree[oud[p]]-Tree[dfn[p]]即可.

对于叶子节点, 我们把它扔到数组里, 并++cnt,注意,非叶节点不会影响cnt

而后就是一个简单的主席树区间第K大查询啦.

注意 : 小心在倍增的时候跳到0点

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2; const int N = 210000;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}struct Edge { int to; Edge *next;}*h[N], e[N<<1];struct Edge1 { int u, v, w; int operator < (const Edge1 &A) const { return w < A.w; }}e1[N*5];int a[N], f[20][N], q[N], rnk[N], fa[N], root[N];int t[N*20], ls[N*20], rs[N*20], val[N], dep[N];int dfn[N], oud[N];inline void addEdge(int u, int v) { static int _; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}void dfs(int p) { for(int i = 1; i < 20; i ++ ) f[i][p] = f[i-1][f[i-1][p]]; dfn[p] = *q; if(!val[p]) q[++*q] = p; rev(i, p) f[0][i->to] = p, dfs(i->to); oud[p] = *q;}void insert(int l, int r, int &p, int q, int x) { static int _; if(!p) p = ++_; t[p] = t[q]+1; if(l == r) return; int mid = (l+r) >> 1; if(x <= mid) rs[p] = rs[q], insert(l, mid, ls[p], ls[q], x); else ls[p] = ls[q], insert(mid+1, r, rs[p], rs[q], x);}int query(int l, int r, int p, int q, int k) { if(l == r) return l; int sizl = t[ls[q]] - t[ls[p]]; int mid = (l+r) >> 1; if(sizl >= k) return query(l, mid, ls[p], ls[q], k); else return query(mid+1, r, rs[p], rs[q], k-sizl);}int main() { int n = rd(), m = rd(), Q = rd(), ans = 0; for(int i = 1; i <= n; i ++ ) a[i] = rd(), rnk[i] = a[i]; sort(rnk+1, rnk+n+1); for(int i = 1; i <= n; i ++ ) a[i] = lower_bound(rnk+1, rnk+n+1, a[i])-rnk; for(int i = 0; i < N; i ++ ) fa[i] = i; for(int i = 1; i <= m; i ++ ) e1[i].u = rd(), e1[i].v = rd(), e1[i].w = rd(); sort(e1+1, e1+m+1); int cnt = n; for(int i = 1; i <= m; i ++ ) { int dx = find(e1[i].u), dy = find(e1[i].v); if(dx != dy) { ++cnt; fa[dx] = cnt; fa[dy] = cnt; val[cnt] = e1[i].w; addEdge(cnt, dx); addEdge(cnt, dy); if(cnt == 2*n-1) break; } } dfs(cnt); for(int i = 1; i <= n; i ++ ) insert(1, n, root[i], root[i-1], a[q[i]]); while(Q -- ) { int v = rd(), x = rd()^ans, k = rd()^ans; int tmp = v^ans; for(int i = 19; ~i; i -- ) if(f[i][tmp] && val[f[i][tmp]] <= x) { tmp = f[i][tmp]; } if(k > oud[tmp] - dfn[tmp]) { puts("-1"); ans = 0; continue; } k = oud[tmp]-dfn[tmp]-k+1; ans = rnk[query(1, n, root[dfn[tmp]], root[oud[tmp]], k)]; printf("%d\n", ans); }}