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

· · 题解

题意简介

对于一个带权无向图，给出 Q 次操作，删除原图上边权小于 val 的边，查询某点所在连通块大小，在保证相对大小不变的情况下修改边权。

思路

考虑对原图建立最大生成树重构树，由于修改时不改变相对大小的特殊性，重构树的结构不会发生变化，故修改操作只需 O ( 1 ) 修改此边对应点的点权。

由重构树的性质，深度较深的点权值更大，在查询操作时，只需树上倍增找到祖先节点中第一个边权 < val 的节点，那么删去这个点对应的边后，其子树内的所有点一定在一个连通块内，答案就是子树内叶子节点个数，单次查询复杂度 O ( n \log n )。

代码实现上有些小细节，比如本题并不保证原图连通，且操作三的修改必须保存到下一次操作一再执行，这是因为题中所说“原来已经断开的关系不会恢复”，若即时实现操作三会破坏上一次操作一的结果。

Code

#include<iostream>
#include<stack>
#include<utility>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=4e5+5;
const int LogN=20;
int n,m,Q,father[N<<1][LogN],dep[N<<1],son[N<<1][2],a[N<<1],siz[N<<1],pre,to[N];
stack<pair<int,int>>operat;
struct Node
{
    int u,v,w;
    Node(int _u=0,int _v=0,int _w=0):u(_u),v(_v),w(_w){}
    bool operator<(const Node &tmp)const
    {
        return w>tmp.w;
    }
}edge[N];
struct Union_Find
{
    int leader[N<<1],point;
    void Init(int n)
    {
        for(int i=1;i<=n;i++)
            leader[i]=i,siz[i]=1;
    }
    int Find(int k)
    {
        if(leader[k]!=k) return leader[k]=Find(leader[k]);
        return k;
    }
    void Merge(int fu,int fv,int val)
    {
        a[++point]=val;
        siz[point]=0;
        son[point][0]=fu;
        son[point][1]=fv;
        leader[fu]=point;
        leader[fv]=point;
        siz[point]+=siz[fu];
        siz[point]+=siz[fv];
    }
}DSU;
void Kruskal_Refactor()
{
    DSU.Init(n<<1);
    DSU.point=n;
    sort(edge+1,edge+m+1);
    for(int i=1;i<=m;i++)
    {
        int fu=DSU.Find(edge[i].u);
        int fv=DSU.Find(edge[i].v);
        if(fu!=fv) DSU.Merge(fu,fv,edge[i].w),to[i]=DSU.point;
    }
}
void Dfs_pre(int u,int fa)
{
    if(!u) return;
    dep[u]=dep[fa]+1,father[u][0]=fa;
    for(int i=1;i<LogN;i++)
        father[u][i]=father[father[u][i-1]][i-1];
    Dfs_pre(son[u][0],u);
    Dfs_pre(son[u][1],u);
}
int Query(int pos,int k)
{
    for(int i=LogN-1;i>=0;i--)
        if(father[pos][i]&&a[father[pos][i]]>=k)
            pos=father[pos][i];
    return siz[pos];
}
int main()
{
    IOS;
    cin>>n>>m>>Q;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        edge[i]=(Node){u,v,w};
    }
    Kruskal_Refactor();
    for(int i=DSU.point;i>=1;i--)
        if(!dep[i]) Dfs_pre(i,0);
    while(Q--)
    {
        int opt,x,val;
        cin>>opt;
        if(opt==1)
        {
            cin>>x,pre=x;
            while(!operat.empty())
                a[to[operat.top().first]]=operat.top().second,operat.pop();
        }
        else if(opt==2)
            cin>>x,cout<<Query(x,pre)<<'\n';
        else
            cin>>x>>val,operat.push({x,val});
    }
    return 0;
}