Blog

题目

Atcoder

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int n, m, q, w[N], p[N], cnt;
int h[N], val[N << 1], ptr[N << 1], idx;
int f[20][N], sz[N];
int find(int x) { return (p[x] == x) ? x : (p[x] = find(p[x])); }
void add(int fa, int a, int b) {
    val[idx] = b, ptr[idx] = h[fa], h[fa] = idx++;
    val[idx] = a, ptr[idx] = h[fa], h[fa] = idx++;
}
void DFS(int u, int fa) {
    f[0][u] = fa;
    for (int i = 1; i <= 19; i++)
        f[i][u] = f[i - 1][f[i - 1][u]];
    if (h[u] == -1) return sz[u] = 1, void(0); // 虚拟父节点不统计大小
    for (int i = h[u], v = val[i]; i != -1; i = ptr[i], v = val[i])
        if (v != fa) DFS(v, u), sz[u] += sz[v];
}
int check(int mid, int x, int y) {
    for (int i = 19; i >= 0; i--) {
        if (w[f[i][x]] <= mid) x = f[i][x];
        if (w[f[i][y]] <= mid) y = f[i][y];
    }
    if (x == y) return sz[x];  // 注意如果相等, 返回一个就行
    else return sz[x] + sz[y];
}
int main() {
    cin >> n >> m;
    memset(h, -1, sizeof h), cnt = n, w[0] = 0x3f3f3f3f;
    for (int i = 1; i <= n * 2; i++) p[i] = i;

    for (int i = 1, a, b; i <= m && cin >> a >> b; i++)
        if ((a = find(a)) != (b = find(b))) // 如果不连通
            // 开父节点记录权值   更新并查集       连边
            w[++cnt] = i, p[a] = p[b] = p[cnt], add(cnt, a, b);
    DFS(cnt, 0); // 初始化倍增和子树大小
    cin >> q;
    for (int x, y, z; q-- && cin >> x >> y >> z; ) {
        int l = 1, r = m;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(mid, x, y) >= z) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}