蒟蒻初学 Kruskal 重构树……
假设没有边权不超过 \(k\) 的限制，这题就变成了永无乡。
但是这里有这么个限制。
考虑离线。
发现在没有这个限制的情况下，找出最小生成树再做对答案没有影响。
于是考虑把询问按照 \(k\) 排序，把边按权值排序后依次尝试插入最小生成树，然后按照永无乡的方法计算答案。
考虑在线。
发现上面的做法就是 K 法的过程。由此我们可以联想到 Kruskal 重构树。
（至于怎么联想到的，参考六学）
其实只要理解了 Kruskal 重构树的性质就很好想了。
代码： 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
using namespace std;
const int N = 1e5;
const int M = 5e5;
const int LG = 20;
int n,m,q,tot;
int lastans;
int a[(N << 1) + 10],ind[(N << 1) + 10],len;
int id[(N << 1) + 10],val[(N << 1) + 10];
int to[(N << 2) + 10],pre[(N << 2) + 10],first[(N << 1) + 10];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
struct edge
{
int u,v,w;
inline bool operator<(const edge &o) const
{
return w < o.w;
}
} e[M + 10];
int fa[(N << 1) + 10];
inline int get(int x)
{
return !fa[x] ? x : fa[x] = get(fa[x]);
}
struct segnode
{
int cnt;
int lson,rson;
} seg[(N << 6) + 10];
int rt[(N << 1) + 10],seg_tot;
int f[(N << 1) + 10][LG + 5],sz[(N << 1) + 10];
void change(int x,int k,int &p,int tl,int tr)
{
seg[++seg_tot] = seg[p];
p = seg_tot;
if(tl == tr)
{
seg[p].cnt += k;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid)
change(x,k,ls(p),tl,mid);
else
change(x,k,rs(p),mid + 1,tr);
seg[p].cnt = seg[ls(p)].cnt + seg[rs(p)].cnt;
}
int query(int k,int p,int q,int tl,int tr)
{
if(tl == tr)
return tl;
int mid = tl + tr >> 1;
int cnt = seg[ls(q)].cnt - seg[ls(p)].cnt;
if(k <= cnt)
return query(k,ls(p),ls(q),tl,mid);
else
return query(k - cnt,rs(p),rs(q),mid + 1,tr);
}
void dfs(int p)
{
static int tot = 0;
sz[p] = 1;
id[p] = ++tot;
if(p <= n)
val[tot] = a[p];
for(register int i = 1;i <= LG;++i)
f[p][i] = f[f[p][i - 1]][i - 1];
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ f[p][0])
{
f[to[i]][0] = p;
dfs(to[i]);
sz[p] += sz[to[i]];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
tot = n;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= m;++i)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e + 1,e + m + 1);
for(register int i = 1;i <= m;++i)
{
int x = e[i].u,y = e[i].v,w = e[i].w;
int fx = get(x),fy = get(y);
if(fx ^ fy)
{
fa[fx] = fa[fy] = ++tot;
add(tot,fx),add(tot,fy);
a[tot] = w;
}
}
for(register int i = 1;i <= tot;++i)
ind[i] = a[i];
sort(ind + 1,ind + tot + 1);
len = unique(ind + 1,ind + tot + 1) - ind - 1;
for(register int i = 1;i <= tot;++i)
a[i] = lower_bound(ind + 1,ind + len + 1,a[i]) - ind;
for(register int i = tot;i;--i)
if(!id[i])
dfs(i);
for(register int i = 1;i <= tot;++i)
{
rt[i] = rt[i - 1];
if(val[i])
change(val[i],1,rt[i],1,len);
}
int v,x,k;
while(q--)
{
scanf("%d%d%d",&v,&x,&k);
v ^= lastans,x ^= lastans,k ^= lastans;
lastans = 0;
int p = v;
for(register int i = LG;i >= 0;--i)
if(f[p][i] && ind[a[f[p][i]]] <= x)
p = f[p][i];
int cnt = seg[rt[id[p] + sz[p] - 1]].cnt - seg[rt[id[p] - 1]].cnt;
if(cnt < k)
puts("-1");
else
printf("%d\n",lastans = ind[query(cnt - k + 1,rt[id[p] - 1],rt[id[p] + sz[p] - 1],1,len)]);
}
}