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

· · 题解

先放一个帖子：link。

这题有一个细节，后面再说。

首先我们发现这个题面十分抽象，所以先提取关键信息，发现没有 3 操作的问题可以转化为：走边权不超过 k 的边能走到多少点，其实也就是瓶颈路问题。

考虑 Kruskal 重构树，则每次能走到的点对应到重构树上刚好就是一个子树，因为 LCA 肯定是瓶颈，既然 LCA 都能走，子树内一定畅通无阻。

那这个方法对于有 3 操作的该题是否有启发呢？答案是显然的。不然我为啥讲。

发现权值的相对关系始终不变，所以树的形态也一定不会变，所以每次修改边权就直接修改 LCA 的点权就行了，不过要提前判断这条边是否在 Kruskal 重构树上，否则只有 90 分。

然后就牵扯到上面的帖子了，题面中说了修改边权不会是断掉的边是不会重连的，所以有些题解的代码有点问题。

具体实现 3 操作的方式有很多，我在代码中选择使用 vector 进行懒删除，每次操作 1 时集体下放修改。

还有就是这道题你不管操作 3 也有 90 分，数据很水。

#include<bits/stdc++.h>

using namespace std;

namespace Fread {
    const int SIZE=1<<21;char buf[SIZE],*S,*T;
    inline char getchar() {if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return '\n';}return *S++;}
}
namespace Fwrite {
    const int SIZE=1<<21;
    char buf[SIZE],*S=buf,*T=buf+SIZE;
    inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
    inline void putchar(char c){*S++=c;if(S==T)flush();}
    struct POPOSSIBLE{~POPOSSIBLE(){flush();}}ztr;
}
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
namespace Fastio{
    struct Reader{
        template<typename T>
        Reader& operator >> (T& x) {
            char c=getchar();T f=1;
            while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}x=0;
            while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}x*=f;
            return *this;
        }
        Reader(){}
    }cin;
    struct Writer{
        template<typename T>
        Writer& operator << (T x) {
            if(x==0){putchar('0');return *this;}
            if(x<0){putchar('-');x=-x;}
            static int sta[45];int top=0;
            while(x){sta[++top]=x%10;x/=10;}
            while(top){putchar(sta[top]+'0');--top;}
            return *this;
        }
        Writer& operator << (char c) {putchar(c);return *this;}
        Writer& operator << (const char* str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}
        Writer(){}
    }cout;
}
#define fi first
#define endl '\n'
#define sec second
#define mk make_pair
#define cin Fastio :: cin
#define cout Fastio :: cout

const int B=20;
const int N=1e6+10;
typedef pair<int,int> pii;
struct edge{
    int x,y,z;
    edge(int x=0,int y=0,int z=0):x(x),y(y),z(z){;}
    bool operator <(const edge &t)const{return z>t.z;}
}a[N],b[N];
int siz[N],f[N][B+1],fa[N],ls[N],rs[N],tot,n,m,q,w[N],las,dep[N];
int root(int x){return x==fa[x]?x:fa[x]=root(fa[x]);}
vector < pii > Q;

void Kruskal(){
    sort(a+1,a+1+m);
    for(int i=1;i<=m;++i){
        int x=root(a[i].x);
        int y=root(a[i].y);
        if(x==y) continue;
        w[++tot]=a[i].z;
        fa[x]=fa[y]=tot;
        ls[tot]=x;rs[tot]=y;
    }
}

void dfs(int x,int y){
    f[x][0]=y;dep[x]=dep[y]+1;
    for(int i=1;i<=B;++i) f[x][i]=f[f[x][i-1]][i-1];
    if(x<=n) siz[x]=1;
    else {
        dfs(ls[x],x);dfs(rs[x],x);
        siz[x]=siz[ls[x]]+siz[rs[x]];
    }
}

inline int LCA(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=B;~i;--i) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=B;~i;--i) if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
    return f[x][0];
} 

inline int jump(int x){
    for(int i=B;~i;--i) if(f[x][i]&&w[f[x][i]]>=las) x=f[x][i];
    return siz[x];
}

int main(){
    cin>>n>>m>>q;tot=n;
    for(int i=1;i<=(n<<1);++i) fa[i]=i;
    for(int i=1;i<=m;++i) cin>>a[i].x>>a[i].y>>a[i].z;
    for(int i=1;i<=m;++i) b[i]=a[i];Kruskal();
    for(int i=tot;i;--i) if(!siz[i]) dfs(i,0);
    for(int i=1,opt,x,y;i<=q;++i){
        cin>>opt>>x;
        if(opt==1){for(auto i:Q) w[i.fi]=i.sec;Q.clear();las=x;}
        else if(opt==2) cout<<jump(x)<<endl;
        else {
            cin>>y;
            int lca=LCA(b[x].x,b[x].y);
            if(w[lca]!=b[x].z) continue;
            Q.emplace_back(lca,b[x].z=y);
        }
    }
    return 0;
}
//这条边有可能本来就没影响。输。