P9638 「yyOI R1」youyou 的军训

_JF_ · 2024-02-23 07:38:09 · 题解

Link

Kuskral 重构树板子。

因为相对边权不变，所以重构树的形态不变。

那其实就是期望连通块内任意两个点路径的最小值最大。重构树内点的点权的含义就是他叶子节点相互抵达的路径上权值最大值。这个我们容易用重构树维护出来，然后实际上我们只用不断地往上跳到 >p 就停止即可。

#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
int n,m,q,siz[N],F[N],fa[N][23],dep[N],lst;
vector<int> g[N];
struct node{
    int u,v,w,id;
}a[N],b[N];
struct edge{
    int id,val;
}c[N];
bool cmp(node a,node b){
    return a.w>b.w;
}
int Find(int x){
    return x==F[x]?x:F[x]=Find(F[x]);
}
void Kuskral_SG(){
    for(int i=1;i<=m;i++)   b[i].u=a[i].u,b[i].v=a[i].v,b[i].w=a[i].w,b[i].id=i;
    sort(b+1,b+m+1,cmp);
    for(int i=1;i<=2*n-1;i++)   F[i]=i;
    int cnt=n;
    for(int i=1;i<=m;i++){
        int u=Find(b[i].u),v=Find(b[i].v);
        if(u==v)    continue;
        cnt++; F[u]=cnt,F[v]=cnt,c[cnt].val=b[i].w,c[cnt].id=b[i].id,g[cnt].push_back(u),g[cnt].push_back(v);
    }
}
void dfs(int u,int fath){
    dep[u]=dep[fath]+1,fa[u][0]=fath;
    if(g[u].size()==0)  siz[u]++;   
    for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(v==fath) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}
int LCA(int x,int y){
    if(dep[x]<dep[y])   swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=22;i>=0;i--)  if((1<<i)&d)    x=fa[x][i];
    if(x==y)    return x;
    for(int i=22;i>=0;i--)  if(fa[x][i]!=fa[y][i])  x=fa[x][i],y=fa[y][i];
    return fa[x][0];    
}
int Query(int x){
    for(int i=22;i>=0;i--)  if(fa[x][i]&&c[fa[x][i]].val>=lst)  x=fa[x][i];
    return siz[x];
}
int main(){
//  freopen("1.in","r",stdin);
//  freopen("ans.out","w",stdout);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)   cin>>a[i].u>>a[i].v>>a[i].w;
    Kuskral_SG();
    for(int i=1;i<=2*n-1;i++)   if(Find(i)==i)  dfs(i,0);
    while(q--){
        int op,x,y;
        cin>>op;
        if(op==1)   cin>>x,lst=x;
        else if(op==2)  cin>>x,cout<<Query(x)<<endl;
        else{
            cin>>x>>y;
            if(c[LCA(b[x].u,b[x].v)].id==x) c[LCA(b[x].u,b[x].v)].val=y;
        }
    }
}