Luogu 4197 [ONTAK2010 Peaks]

传送门
垃圾BZOJ,又过不了我的大常数。


题目大意

给你一个$N\le 10^5$个点$M\le 5\times 10^5$条边的无向图,每条边有边权,每个点有点权。
每次给你一组$v,x,k$,询问从$v$开始经过不超过$x$的路可以走到的所有点中的第$k$大。
无解输出$-1$。

解析

显然这个东西是在最小生成树上跑。
这个不超过$x$的东西有一类方法。
这个东西叫做Kruskal重构树

Kruskal重构树

我们考虑把边改成点。
还是Kruskal求最小生成树的过程,但是我们“不加边”。
方便表达,下面说的都是代表了联通块的节点。
具体来说,假设我们现在要吧$u,v$之间权值为$w$的边弄到最小生成树中去。
那么我们就new一个$fa$,让这个$fa$的权值为$w$,然后这个$fa$向$u,v$连边。
容易发现,这样我们就会new出一颗新树来,这棵树就是Kruskal重构树。

那么这棵树有两个非常好的性质:

  1. 原生成树的节点都是叶子节点(显然)
  2. 非叶子节点的权值一定不超过其父亲的权值(按Kruskal的顺序加边,自然后来的边权值不小于先来的边)
    所以说,从一个点出发,只要找到它的权值不超过$x$最老祖先,然后以它为根的子树的所有叶子节点就都可以到了。

这题要求$kth$,套一个主席树就可以啦。
细节稍微注意一下。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#define  REP(i, s, e) for (int i = s; i <= e; i++)
#define DREP(i, s, e) for (int i = s; i >= e; i--)
#define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)

#define chkmax(a, b) a = max(a, (b))
#define chkmin(a, b) a = min(a, (b))

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <queue>

using namespace std;
const int maxn = 1e5 + 10, maxm = 5e5 + 10, n_log_n = 3600000;

int bg[maxn << 1], to[maxm], ne[maxm], e;
inline void add(int x, int y)
{
e++;
to[e] = y;
ne[e] = bg[x];
bg[x] = e;
}
int fa[maxn << 1];
int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}

void file(string s)
{
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}

int n, m, q, cur, M;
int val[maxn << 1];
struct Edge
{
int x, y, z;
Edge() {}
Edge(int _x, int _y, int _z) : x(_x), y(_y), z(_z) {}
}E[maxm];
bool cmp(Edge A, Edge B) {return A.z < B.z;}

int N, grand[maxn << 1][25], LOG, Left[maxn << 1], Right[maxn << 1];
int dfn[maxn], dfs_clock, vv[maxn];

void prepare(int x)
{
if (x <= n) vv[Left[x] = Right[x] = dfn[x] = ++dfs_clock] = val[x];
bool flag = 0;
for (int i = bg[x]; i ; i = ne[i])
if (to[i] ^ grand[x][0])
{
grand[to[i]][0] = x;
prepare(to[i]);
if (x > n)
if (!flag) {Left[x] = Left[to[i]];Right[x] = Right[to[i]];flag = 1;}
else
{
chkmin(Left[x], Left[to[i]]);
chkmax(Right[x], Right[to[i]]);
}
}
}
void output(int x)
{
for (int i = bg[x]; i ; i = ne[i])
if (to[i] ^ grand[x][0])
{
printf("%d %d\n", x, to[i] <= n&&0 ? dfn[to[i]] : to[i]);
output(to[i]);
}
}

int a[maxn], b[maxn];

int rt[n_log_n], ls[n_log_n], rs[n_log_n], sum[n_log_n], nd_cur;

#define mid (l + r >> 1)
#define lson ls[p], l, mid
#define rson rs[p], mid + 1, r

void build(int pre, int &p, int l, int r, int pos)
{
p = ++nd_cur;
ls[p] = ls[pre];
rs[p] = rs[pre];
sum[p] = sum[pre] + 1;
if (l == r) return;
if (pos <= mid) build(ls[pre], lson, pos);
else build(rs[pre], rson, pos);
}

int query(int u, int v, int l, int r, int k)
{
if (l >= r) return l;
int x = sum[ls[v]] - sum[ls[u]];
if (x < k) return query(rs[u], rs[v], mid + 1, r, k - x);
else return query(ls[u], ls[v], l, mid, k);
}

int main()
{
#ifdef CraZYali
file("4197");
#endif
cin >> n >> m >> q;cur = n;
REP(i, 1, n) scanf("%d", val + i);
REP(i, 1, n * 2) fa[i] = i;
REP(i, 1, m)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
E[i] = Edge(x, y, z);
}
sort(E + 1, E + 1 + m, cmp);
int cnt = 0;
REP(i, 1, m)
{
int x(find(E[i].x)), y(find(E[i].y));
if (x ^ y)
{
val[++cur] = E[i].z;
add(cur, x);
add(cur, y);
fa[x] = fa[y] = cur;
if (++cnt == n - 1) break;
}
}
N = n + n - 1;
prepare(cur);
LOG = log2(N);
REP(j, 1, LOG)
REP(i, 1, N)
grand[i][j] = grand[grand[i][j-1]][j-1];
// REP(i, n+1, N)
// printf("%d %d %d\n", i, Left[i], Right[i]);
// output(cur);
REP(i, 1, n) a[i] = b[i] = vv[i];
// al[dfn[i]];
sort(b + 1, b + 1 + n);
M = unique(b + 1, b + 1 + n) - b - 1;
REP(i, 1, n) build(rt[i-1], rt[i], 1, M, lower_bound(b + 1, b + 1 + M, a[i]) - b);
// REP(i, 1, n) printf("%d%c", dfn[i], i == n ? '\n' : ' ' );
// REP(i, 1, n) printf("%d%c", vv[i], i == n ? '\n' : ' ' );
// REP(i, 1, n) printf("%d%c", a[i], i == n ? '\n' : ' ' );
// REP(i, 1, M) printf("%d%c", b[i], i == M ? '\n' : ' ' );
// REP(i, 1, n) printf("%d%c", lower_bound(b+1,b+1+M,a[i])-b, i == n ? '\n' : ' ' );
// REP(i, 1, n)
// REP(j, i, n)
// REP(k, 1, j - i + 1)
// printf("%d %d %d %d\n", i, j, k, b[query(T[i-1], T[j], 1, M, k)]);
while (q--)
{
int v, x, k;
scanf("%d%d%d", &v, &x, &k);
// cout << v << " -> ";
DREP(i, LOG, 0)
if (!grand[v][i]) continue;
else if (val[grand[v][i]] <= x) v = grand[v][i];
// cout << v << "\n";
// cout << Left[v] << ' ' << Right[v] << endl;
int len = Right[v] - Left[v] + 1;
printf("%d\n", k > len ? - 1 : b[query(rt[Left[v]-1], rt[Right[v]], 1, M, len - k + 1)]);
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×