LUOGU P1967 货车运输(最大生成树+树剖+线段树)

传送门

解题思路

货车所走的路径一定是最大生成树上的路径，所以先跑一个最大生成树，之后就是求一条路径上的最小值，用树剖+线段树，注意图可能不连通。将边权下放到点权上，但x,y路径上的lca的答案不能算，因为他的点权来自上面的路径。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = ;

const int inf = 0x3f3f3f3f;

inline int rd(){

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}

    while(isdigit(ch))  {x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return f?x:-x;

}

int n,m,head[MAXN],cnt,to[MAXN<<],nxt[MAXN<<],w[MAXN],Fa[MAXN],val[MAXN<<];

int fa[MAXN],dep[MAXN],id[MAXN],wt[MAXN],top[MAXN],siz[MAXN],son[MAXN];

int Min[MAXN<<],num,q;

bool vis[MAXN];

struct Node{

    int u,v,z;

}node[MAXN];

inline bool cmp(Node A,Node B){

    return A.z>B.z;

}

int get(int x){

    if(x==Fa[x]) return x;

    return Fa[x]=get(Fa[x]);

}

inline void add(int bg,int ed,int ww){

    to[++cnt]=ed,nxt[cnt]=head[bg],val[cnt]=ww,head[bg]=cnt;

}

void dfs1(int x,int f,int d){

    fa[x]=f,dep[x]=d,siz[x]=,vis[x]=;

    int maxson=-,u;

    for(register int i=head[x];i;i=nxt[i]){

        u=to[i];if(u==f) continue;

        w[u]=val[i];dfs1(u,x,d+);

        siz[x]+=siz[u];

        if(siz[u]>maxson) {maxson=siz[u];son[x]=u;}

    }

}

void dfs2(int x,int topf){

    id[x]=++num;wt[num]=w[x];top[x]=topf;

    if(!son[x]) return;

    dfs2(son[x],topf);int u;

    for(register int i=head[x];i;i=nxt[i]){

        u=to[i];if(u==fa[x] || u==son[x]) continue;

        dfs2(u,u);

    }

}

void build(int x,int l,int r){

    if(l==r) {

        Min[x]=wt[l];

        return;

    }

    int mid=(l+r)>>;

    build(x<<,l,mid),build(x<<|,mid+,r);

    Min[x]=min(Min[x<<],Min[x<<|]);

}

int query(int x,int l,int r,int L,int R){

    if(L<=l && r<=R) return Min[x];

    int mid=l+r>>,ret=inf;

    if(L<=mid) ret=min(ret,query(x<<,l,mid,L,R));

    if(mid<R)  ret=min(ret,query(x<<|,mid+,r,L,R));

    return ret;

}

int qRange(int x,int y){

    int u=get(x),v=get(y),ret=inf;

    if(u!=v) return -;

    while(top[x]!=top[y]){

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        ret=min(ret,query(,,n,id[top[x]],id[x]));

        x=fa[top[x]];

    }

    if(x==y) return ret;

    if(dep[x]>dep[y]) swap(x,y);

    ret=min(ret,query(,,n,id[x]+,id[y]));

    return ret;

}

int main(){

    n=rd(),m=rd();int x,y;

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

    for(int i=;i<=m;i++) node[i].u=rd(),node[i].v=rd(),node[i].z=rd();

    sort(node+,node++m,cmp);int uu,vv;

    for(int i=;i<=m;i++){

        uu=get(node[i].u),vv=get(node[i].v);

        if(uu!=vv) {

            Fa[uu]=vv;

            add(node[i].u,node[i].v,node[i].z);

            add(node[i].v,node[i].u,node[i].z);

        }

    }

    for(int i=;i<=n;i++)

        if(!vis[i]) {w[i]=inf;dfs1(i,,);dfs2(i,i);}

    q=rd();build(,,n);

    while(q--){

        x=rd(),y=rd();

        printf("%d\n",qRange(x,y));

    }

    return ;

}