P9638 「yyOI R1」youyou 的军训 题解

happybob · 2023-09-17 18:04:52 · 题解

Kruskal 重构树板子。

考虑建边权从大到小排序后跑 Kruskal 的重构树，对于当前点 u 和参数 w，只能走 \geq w 边，即能去的点是 u 祖先中最浅的点权 \geq w 的点所在子树内每个叶子节点。

发现边权修改后，相对大小不变，直接在重构树点权修改即可。

倍增处理，复杂度 O(q \log n)。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;

const int N = 8e5 + 5;
int p[N];

struct Edge
{
    int u, v, w;

    Edge() = default;

    Edge(int u, int v, int w)
        : u(u), v(v), w(w)
    {
    }

    bool operator==(const Edge& other) const
    {
        return u == other.u && v == other.v && w == other.w;
    }
}e[N];

int n, m, q;
int u[N], v[N], w[N];
int res[N];
int nfa[N][21];
map<pair<int, int>, int> mp;

class Union_Find
{
public:
    int fa[N], idx;
    int val[N], res[N];
    vector<int> G[N];
    void Init()
    {
        mp.clear();
        for (int i = 0; i < N; i++) fa[i] = i, val[i] = 0, G[i].clear();
        for (int i = 1; i <= n; i++) res[i] = 1;
        idx = n;
    }
    int find(int u)
    {
        return (fa[u] == u ? u : fa[u] = find(fa[u]));
    }
    void merge(int u, int v, int w)
    {
        if (find(u) == find(v)) return;
        mp[make_pair(u, v)] = ++idx;
        u = find(u), v = find(v);
        val[idx] = w;
        G[idx].emplace_back(u), G[idx].emplace_back(v);
        nfa[u][0] = nfa[v][0] = idx;
        fa[u] = fa[v] = idx;
        res[idx] += res[u] + res[v];
    }
}uf;

int val[N];
vector<int> G[N];

void kruskal()
{
    uf.Init();
    sort(e + 1, e + m + 1, [&](const Edge& x, const Edge& y) {return x.w > y.w; });
    for (int i = 1; i <= m; i++) uf.merge(e[i].u, e[i].v, e[i].w);
    for (int i = 0; i < N; i++) val[i] = uf.val[i], G[i].swap(uf.G[i]);
}

int get(int u, int x)
{
    for (int i = 20; i >= 0; i--)
    {
        if (nfa[u][i] && val[nfa[u][i]] >= x) u = nfa[u][i];
    }
    return u;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
        e[i] = Edge(u[i], v[i], w[i]);
    }
    kruskal();
    for (int i = 1; i <= 20; i++)
    {
        for (int j = 0; j < N; j++) nfa[j][i] = nfa[nfa[j][i - 1]][i - 1];
    }
    for (int i = 0; i < N; i++) res[i] = uf.res[i];
    int now = 0;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            cin >> now;
        }
        else if (op == 2)
        {
            int x;
            cin >> x;
            cout << res[get(x, now)] << "\n";
        }
        else
        {
            int x, y;
            cin >> x >> y;
            if (mp.count(make_pair(u[x], v[x])))
            {
                val[mp[make_pair(u[x], v[x])]] = y;
            }
        }
    }
    return 0;
}