Luogu4197 Peaks

题目链接：洛谷

---

看到“只经过困难值小于等于$x$的路径”。

感觉有点眼熟。

ow，就是[NOI2018]归程。

---

和那道题一样，可以直接建出Kruskal重构树，每次倍增寻找祖先中最上面的不大于$x$的节点$v$，$v$的子树就是可以到达的范围。

根据Kruskal重构树的dfs序建出主席树求第$K$大。

 #include<cstdio>

 #include<algorithm>

 #define Rint register int

 using namespace std;

 const int N = ;

 struct Edge {

     int u, v, w;

     inline bool operator < (const Edge &o) const {return w < o.w;}

 } e[N];

 int n, m, q, _n, h[N], b[N], val[N], head[N], to[N << ], nxt[N << ], fa[N], tot;

 inline int getfa(int x){return x == fa[x] ? x : fa[x] = getfa(fa[x]);}

 inline void add(int a, int b){

     static int cnt = ;

     to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;

 }

 int root[N], ls[N << ], rs[N << ], seg[N << ], cnt;

 inline void change(int &now, int pre, int L, int R, int pos){

     now = ++ cnt; seg[now] = seg[pre] + ;

     if(L == R) return;

     int mid = L + R >> ;

     if(pos <= mid) rs[now] = rs[pre], change(ls[now], ls[pre], L, mid, pos);

     else ls[now] = ls[pre], change(rs[now], rs[pre], mid + , R, pos);

 }

 inline int query(int nowl, int nowr, int L, int R, int k){

     if(L == R) return L;

     int mid = L + R >> , minused = seg[rs[nowr]] - seg[rs[nowl]];

     if(k <= minused) return query(rs[nowl], rs[nowr], mid + , R, k);

     else return query(ls[nowl], ls[nowr], L, mid, k - minused);

 }

 int st[][N], dfn[N], out[N], tim;

 inline void dfs(int x){

     dfn[x] = ++ tim;

     if(x <= n) change(root[dfn[x]], root[dfn[x] - ], , _n, h[x]);

     else root[dfn[x]] = root[dfn[x] - ];

     for(Rint i = head[x];i;i = nxt[i]) dfs(to[i]);

     out[x] = tim;

 }

 inline int query(int v, int x, int k){

     for(Rint i = ;~i;i --)

         if(st[i][v] && val[st[i][v]] <= x) v = st[i][v];

     int lx = root[dfn[v] - ], rx = root[out[v]];

     return seg[rx] - seg[lx] >= k ? b[query(lx, rx, , _n, k)] : -;

 }

 int main(){

     scanf("%d%d%d", &n, &m, &q); tot = n;

     for(Rint i = ;i <= n;i ++) scanf("%d", h + i), b[i] = h[i];

     sort(b + , b + n + );

     _n = unique(b + , b + n + ) - b - ;

     for(Rint i = ;i <= n;i ++) h[i] = lower_bound(b + , b + _n + , h[i]) - b;

     for(Rint i = ;i <= m;i ++)

         scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

     sort(e + , e + m + );

     for(Rint i = ;i <= n;i ++) fa[i] = i;

     for(Rint i = ;i <= m && tot < (n << ) - ;i ++){

         int fa1 = getfa(e[i].u), fa2 = getfa(e[i].v);

         if(fa1 != fa2){

             ++ tot;

             fa[tot] = fa[fa1] = fa[fa2] = tot;

             st[][fa1] = st[][fa2] = tot;

             add(tot, fa1); add(tot, fa2);

             val[tot] = e[i].w;

         }

     }

     for(Rint i = tot;i;i --) if(!dfn[i]) dfs(i);

     for(Rint i = ;i <= ;i ++)

         for(Rint j = ;j <= tot;j ++) st[i][j] = st[i - ][st[i - ][j]];

     while(q --){

         int v, x, k;

         scanf("%d%d%d", &v, &x, &k);

         printf("%d\n", query(v, x, k));

     }

 }

Luogu4197