P2245-LCA

注意图不一定联通

#include <bits/stdc++.h>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define SZ(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

using ll=long long;

struct dsu{
    vi fa,sz;
    dsu(int n){
        fa.resize(n+1),sz.resize(n+1);
        for(int i=1;i<=n;++i)fa[i]=i,sz[i]=1;
    }
    int fnd(int x){
        return fa[x]==x?x:fa[x]=fnd(fa[x]);
    }
    bool merge(int x ,int y){
        int oa=fnd(x),ob=fnd(y);
        if(oa!=ob){
            fa[ob]=oa,sz[oa]+=sz[ob];
            return true;
        }
        return false;
    }
};

int n,m,q,hd[(int)1e5+9],tot=1,lg[(int)1e5+9],d[(int)1e5+9],fa[(int)1e5+9][21],dp[(int)1e5+9][21]; 
struct Edge{
    int to,nxt,w;
}e[(int)1e6+9];

void add(int u,int v,int w){
    e[++tot]={v,hd[u],w},hd[u]=tot;
    e[++tot]={u,hd[v],w},hd[v]=tot;
}

void dfs(int u,int pre,int lst){
    fa[u][0]=pre,d[u]=d[pre]+1,dp[u][0]=lst;
    for(int i=1;i<=lg[d[u]];++i)fa[u][i]=fa[fa[u][i-1]][i-1],dp[u][i]=max({dp[u][i-1],dp[fa[u][i-1]][i-1]});
    for(int eg=hd[u];eg;eg=e[eg].nxt)if(e[eg].to!=pre)dfs(e[eg].to,u,e[eg].w);
}


int LCA(int x,int y){
    int res=0;
    if(d[x]<d[y])swap(x,y);
    while(d[x]>d[y])res=max(res,dp[x][lg[d[x]-d[y]]]),x=fa[x][lg[d[x]-d[y]]];
    if(x==y)return res;
    for(int k=lg[d[x]];k>=0;--k)if(fa[x][k]!=fa[y][k])res=max({res,dp[x][k],dp[y][k]}),x=fa[x][k],y=fa[y][k];
    return max({dp[x][0],dp[y][0],res});
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<array<int,3>>edge;
    cin>>n>>m;
    for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
    dsu d(n);

    for(int i=1,x,y,z;i<=m;++i){
        cin>>x>>y>>z;
        edge.push_back({x,y,z});
    }
    sort(all(edge),[](array<int,3> aa,array<int,3> bb){return aa[2]<bb[2];});
    for(auto [aa,bb,cc]:edge)if(d.merge(aa,bb))add(aa,bb,cc);
    for(int i=1;i<=n;++i)if(d.fnd(i)==i)dfs(i,0,0);
    
    cin>>q;
    for(int i=1,x,y;i<=q;++i){
        cin>>x>>y;
        if(d.fnd(x)!=d.fnd(y))cout<<"impossible\n";
        else cout<<LCA(x,y)<<"\n";
    }
    return 0;
}