#F7. 城市生长

    ID: 8 传统题 2000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>数据结构并查集树结构生成树树上倍增其他排序

城市生长

T3 城市生长(rebuild)

时间限制:2.0 秒 空间限制:256 MB

题目描述

有 nn 座城市,编号为 1,2,…,n1,2,\dots,n。起初城市之间没有任何道路。接下来有 mm 条道路会依次建成,第 ii 条道路连接城市 uiu_i 和 viv_i,建成时间为 tit_i。道路是双向的,建成后可以立即通行。可能存在重边,但不会出现自环。

城市之间的连通性会随时间变化。现在有 qq 次询问,第 jj 次询问给出城市 uu 和整数 kk:

求最早的日期 dd,使得在日期 dd 结束时(即所有满足 ti≤dt_i\le d 的道路都建成后),城市 uu 所在的连通块中至少有 kk 座城市。

如果不存在这样的日期,输出 −1-1。特别地,当 k=1k=1 时答案为 00(不需要任何道路,城市 uu 自己就构成一个大小为 11 的连通块)。

输入格式

第一行三个正整数 n,m,qn,m,q。

接下来 mm 行,每行三个正整数 ui,vi,tiu_i,v_i,t_i,表示一条连接 uiu_i 和 viv_i、建成时间为 tit_i 的道路。

接下来 qq 行,每行两个正整数 u,ku,k,表示一次询问。

输出格式

输出 qq 行,每行一个整数表示对应询问的答案。

样例 1

输入:

3 2 5
1 2 2
2 3 5
1 2
1 3
2 3
3 2
1 1

输出:

2
5
5
5
0

样例 1 解释: 第 22 天道路 1−21-2 建成,城市 1,21,2 连通;第 55 天道路 2−32-3 建成,三座城市全部连通。因此城市 11 的连通块达到大小 22 的最早日期是 22,达到大小 33 的最早日期是 55;城市 2,32,3 的情况同理;k=1k=1 时答案为 00。

样例 2

输入:

4 2 5
1 2 1
3 4 2
1 2
1 3
3 2
1 1
2 4

输出:

1
-1
2
0
-1

样例 2 解释: 第 11 天城市 1,21,2 连通,第 22 天城市 3,43,4 连通,但两组城市之间始终没有道路。因此城市 11 的连通块永远无法达到大小 33,城市 22 的连通块永远无法达到大小 44;城市 33 的连通块在第 22 天达到大小 22。

数据范围

对于全部测试数据:1≤n≤2×1051\le n\le 2\times 10^5;0≤m≤4×1050\le m\le 4\times 10^5;1≤q≤2×1051\le q\le 2\times 10^5;1≤ti≤1091\le t_i\le 10^9;1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i;1≤u,k≤n1\le u,k\le n。

子任务

子任务 分值 特殊限制
1 20 n,m,q≤2000n,m,q\le 2000
2 所有 tit_i 相等
3 m=n−1m=n-1,且最终所有城市连通
4 40 无特殊限制

提示: 注意 k=1k=1 的询问;答案只与城市 uu 所在的连通块有关,与另一座城市无关。