题解：P9638 「yyOI R1」youyou 的军训

· · 题解

\texttt{solve}

考虑是否适用于 kruskal 重构树，不难发现修改的限制条件“不改变相对顺序”就是防止重构树的形状发生改变设计的，只用单纯修改重构树上点权即可。

简单来说，这题就是瓶颈路问题的板子。

首先考虑跑一遍最大生成树。因为对于一个连接两个联通块的边 x\leftrightarrow y，若其权值 z 小于另一条同样连接这个联通块的 x'\leftrightarrow y' 的权值 z'，当 x'\leftrightarrow y' 因为小于敏感度断掉时，x\leftrightarrow y 一定也断掉。因为没有边长这一说，所以这样选一定是不劣的。

进行操作一时，不妨先用一个变量 limit 记录。初始设置为 -\infty，这样不会有边断掉。

此时考虑在 limit 的限制条件下进行操作 2。本质上就是寻找最大瓶颈，即找到 x 的最浅祖先结点满足该结点的权值 \ge limit。此时该子树内所有结点都在一个联通块里，叶子结点数量即为答案。

对于操作三，我们找到对应原边后修改这两个点的 \text{lca} 的权值即可。但是需要注意的是，因为这条边就算变大如果已经断掉了也不会恢复，那么我们需要把这个修改（如果有效）先存起来，进行新的操作一后更新。

排序建 kruskal 重构树是 O(m\log m+m)，修改找原边用映射 O(n)，求 \text{lca} 用树剖 O(\log n)，倍增找瓶颈 O(\log n)，跑 dfs 挂权值和树剖均是 O(n)。最劣的时间复杂度为 O(m\log m+m+n+q\log n)。

\texttt{tips}

\texttt{code}

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define ldouble long double
#define endl '\n'
using namespace std;
const int N = 4e5+5;

struct edge{
    int idx,x,y,z;
    bitset<1> is;

    edge(int a = 0,int b = 0,int c = 0,int d = 0):
        idx(a),x(b),y(c),z(d) {}

    bool operator <(const edge &other) const {
        return this->z < other.z;
    }
    bool operator >(const edge &other) const {
        return this->z > other.z;
    }
}e[N];
int table[N];

struct node{
    int x,y,z;
}history[N];
int cnt;

int n,m,q;
int f[N<<1];
int limit;

vector<int > g[N<<1];
int cntId,id[N<<1];
int fa[N<<1][30],dep[N<<1];
int sz[N<<1],wson[N<<1];
int top[N<<1],val[N<<1];
int cntLeaves[N<<1];

inline int find(int x){
    if(f[x] == x) return x;
    return f[x] = find(f[x]);
}

inline void dfs1(int x,int father){
    fa[x][0] = father,sz[x] = 1;
    dep[x] = dep[father] + 1;
    for(int y : g[x]){
        if(y == father)
            continue;
        dfs1(y,x);
        sz[x] += sz[y];
        if(sz[y] > sz[wson[x]])
            wson[x] = y;
    }
}

inline void dfs2(int x,int TOP){
    id[x] = ++cntId;
    top[x] = TOP;
    if(wson[x]){
        dfs2(wson[x],TOP);
        cntLeaves[x] += cntLeaves[wson[x]];
    }else cntLeaves[x] = 1;
    for(int y : g[x]){
        if(y != fa[x][0] && y != wson[x]){
            dfs2(y,y);
            cntLeaves[x] += cntLeaves[y];
        }
    }
}

inline int lca(int x,int y){
    if(find(x) != find(y))
        return 0;

    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]])
            swap(x,y);
        x = fa[top[x]][0];
    }
    return dep[x] < dep[y] ? x : y;
}

inline int query(int x){
    int idx = 0;
    while(fa[x][idx] && val[fa[x][idx]] >= limit)
        idx++;

    if(idx == 0) return 1;

    idx--;
    while(idx >= 0){
        if(val[fa[x][idx]] >= limit)
            x = fa[x][idx];
        idx--;
    }

    return cntLeaves[x];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> q;

    int x,y,k;
    for(int i = 1; i <= m; i++){
        cin >> x >> y >> k;
        e[i] = edge(i,x,y,k);
        e[i].is.reset();
    }

    sort(e+1,e+1+m,greater<edge>());

    for(int i = 1; i <= (n<<1); i++)
        f[i] = i;

    for(int i = 1; i <= m; i++)
        table[e[i].idx] = i;

    int cntNode = n;
    for(int i = 1; i <= m; i++){
        int x = e[i].x,y = e[i].y;
        int fx = find(x),fy = find(y);
        if(fx != fy){
            e[i].is.set();
            val[++cntNode] = e[i].z;
            f[fx] = cntNode,f[fy] = cntNode;
            g[fx].push_back(cntNode),g[cntNode].push_back(fx);
            g[fy].push_back(cntNode),g[cntNode].push_back(fy);
        }
        if(cntNode == (n<<1)-1)
            break;
    }

    val[0] = -1;
    for(int idx = cntNode; idx >= 1; idx--){
        if(!id[idx]){
            dfs1(idx,0);
            dfs2(idx,idx);
        }
    }

    for(int j = 1; (1<<j) <= (n<<1); j++)
        for(int i = 1; i <= (n<<1); i++)
            fa[i][j] = fa[fa[i][j-1]][j-1];
    int op;
    while(q--){
        cin >> op;
        if(op == 1){
            cin >> x;
            limit = x;

            for(int i = 1; i <= cnt; i++)
                val[lca(history[i].x,history[i].y)] = history[i].z;
            cnt = 0;
        }else if(op == 2){
            cin >> x;
            cout << query(x) << endl;
        }else if(op == 3){
            cin >> x >> y;
            edge p = e[table[x]];
            if(p.is == true)
                history[++cnt] = (node){p.x,p.y,y};
        }
    }
    return 0;
}