CF1628E Groceries in Meteor Town 题解

题目链接

点击打开链接

题目解法

感觉就是很多个套路组合出来，但我有些套路都不会/ll

• 套路1
  看到从一点出发，到其他点的路径上的最大权，可以想到 \(kruskal\) 生成树（这提示我不仅是图可以用 \(kruskal\) 生成树，树也可以捏）
  我们建大根的 \(kruskal\) 生成树，那么将问题转化成了找一个白点 \(y\)，使得 \(lca(x,y)\) 的深度最小
• 套路2
  对于固定的点 \(x\)，在一个点集 \(S\) 中选出 \(y\)，使得 \(lca(x,y)\) 的深度最小，那么 \(y\) 一定出自点集 \(S\) 中 \(dfs\) 序最小和最大的 \(2\) 个点之一
  这个结论不难感性理解
  这启发我们只要维护当前白点中最小和最大的 \(dfs\) 序的点即可

时间复杂度 \(O(n\log n)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=600100;
int n,m,V[N];
int lc[N],rc[N],fa[N],up[N][20],depth[N],dfs_clock,dfn[N];
typedef tuple<int,int,int> tup;
tup E[N];
void dfs(int u){
    dfn[u]=++dfs_clock;
    if(lc[u]){
        depth[lc[u]]=depth[rc[u]]=depth[u]+1;
        dfs(lc[u]),dfs(rc[u]);
    }
}
#define fi first
#define se second
struct SGT{
    pii sto[N<<2],seg[N<<2];
    int tag[N<<2];
    void down(int x,int type){
        tag[x]=type;
        if(type) seg[x]=sto[x];
        else seg[x]={-1,-1};
    }
    void pushdown(int x){ if(tag[x]!=-1) down(x<<1,tag[x]),down(x<<1^1,tag[x]),tag[x]=-1;}
    int Upmx(int x,int y){ if(x==-1) return y;if(y==-1) return x;return dfn[x]>dfn[y]?x:y;}
    int Upmn(int x,int y){ if(x==-1) return y;if(y==-1) return x;return dfn[x]<dfn[y]?x:y;}
    pii pushup(pii o1,pii o2){ return {Upmx(o1.fi,o2.fi),Upmn(o1.se,o2.se)};}
    void build(int l,int r,int x){
        tag[x]=-1,seg[x]={-1,-1};
        if(l==r){ sto[x]={l,l};return;}
        int mid=(l+r)>>1;
        build(l,mid,x<<1),build(mid+1,r,x<<1^1);
        sto[x]=pushup(sto[x<<1],sto[x<<1^1]);
    }
    void modify(int l,int r,int x,int L,int R,int type){
        if(L<=l&&r<=R){ down(x,type);return;}
        pushdown(x);
        int mid=(l+r)>>1;
        if(mid>=L) modify(l,mid,x<<1,L,R,type);
        if(mid<R) modify(mid+1,r,x<<1^1,L,R,type);
        seg[x]=pushup(seg[x<<1],seg[x<<1^1]);
    }
}sgt;
int Lca(int x,int y){
    if(depth[x]>depth[y]) swap(x,y);
    DF(i,19,0) if(depth[up[y][i]]>=depth[x]) y=up[y][i];
    if(x==y) return x;
    DF(i,19,0) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i];
    return up[x][0];
}
int get_father(int x){ return x==fa[x]?x:fa[x]=get_father(fa[x]);}
int main(){
    n=read(),m=read();
    F(i,1,n-1){
        int x=read(),y=read(),z=read();
        E[i]={z,x,y};
    }
    sort(E+1,E+n);
    int ext=n;
    F(i,1,n) fa[i]=i;
    F(i,1,n-1){
        auto [z,x,y]=E[i];
        x=get_father(x),y=get_father(y);
        ext++,V[ext]=z;
        up[x][0]=up[y][0]=ext,fa[x]=fa[y]=fa[ext]=ext;
        lc[ext]=x,rc[ext]=y;
    }
    depth[ext]=1,dfs(ext);
    F(j,1,19) F(i,1,ext) up[i][j]=up[up[i][j-1]][j-1];
    sgt.build(1,n,1);
    while(m--){
        int op=read();
        if(op==1){ int l=read(),r=read();sgt.modify(1,n,1,l,r,1);}
        else if(op==2){ int l=read(),r=read();sgt.modify(1,n,1,l,r,0);}
        else{
            int x=read();
            auto [p1,p2]=sgt.seg[1];
            int ans=-1;
            if(p1!=x&&p1!=-1) chkmax(ans,V[Lca(p1,x)]);
            if(p2!=x&&p2!=-1) chkmax(ans,V[Lca(p2,x)]);
            printf("%d\n",ans);
        }
    }
    return 0;
}