题目链接

分析

NOIp的一道裸题,直接在最大生成树上剖分取最小值一下就完事了，非常好写,常数也比较小，然而题解里有许多我没见过的船新操作,先挖个坑等有时间再看

注意

• 树链剖分又在第一遍挂了,忘了写top[now]=t;

• 注意题目说明并没有保证是联通的!!!然后成功被Hack了.这真的要警惕,指不定哪天毒瘤出题人就在这里把你正解卡成60(flag++)

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long ong #define ri register int #define ull unsigned long long using std::vector;using std::swap;using std::min;using std::max;using std::sort;template 
           
            inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x;return ;}const int maxn=10005;const int maxm=50005;const int inf=0x7fffffff;int n,m;struct Edge{ int x,y,c; Edge(int _x,int _y,int _c){x=_x,y=_y,c=_c;} Edge(){x=y=c=0;} bool operator <(const Edge &b)const { return c>b.c; } }edge[maxm];struct Dat{ int ver,dis; Dat(int x,int y){ver=x,dis=y;} Dat(){;}};vector
            
             g[maxn]; int pa[maxn];int get(int x){ if(pa[x]!=x)pa[x]=get(pa[x]);//return pa[x]==x?pa[x]:pa[x]=get(pa[x]); return pa[x];}inline void kruskal(){ int cnt=0,x,y,xx,yy,c; sort(edge+1,edge+1+m); for(ri i=1;i<=n;i++)pa[i]=i; for(ri i=1;i<=m;i++){ //printf("%d\n",edge[i].c); int x=edge[i].x,y=edge[i].y; xx=get(x),yy=get(y); if(xx==yy)continue; c=edge[i].c; //printf("%d %d %d\n",x,y,c); g[x].push_back(Dat(y,c)); g[y].push_back(Dat(x,c)); pa[xx]=yy; cnt++; if(cnt==n-1)break; } return ;}int dep[maxn],son[maxn],top[maxn],size[maxn],dfn[maxn],fa[maxn],rnk[maxn],tot=0;int w[maxn];void dfs_1(int now){ int v;size[now]=1; for(ri i=0;i
             
              size[son[now]])son[now]=v; } return ;}void dfs_2(int now,int t){ int v;dfn[now]=++tot,rnk[tot]=now,top[now]=t; if(!son[now])return ; dfs_2(son[now],t); for(ri i=0;i
              
               >1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); mi[now]=min(mi[now<<1],mi[now<<1|1]); return ;}int L,R;int query(int now,int l,int r){ if(L<=l&&r<=R){ return mi[now]; } int ans=inf,mid=(l+r)>>1; if(L<=mid)ans=min(ans,query(now<<1,l,mid)); if(mid
               
                <<1|1,mid+1,r)); return ans;}inline int query_path(int x,int y){ int ans=inf; while(top[x]!=top[y]){ if(dep[top[x]]
                
                 dfn[y])swap(x,y); L=dfn[x]+1,R=dfn[y]; if(L>R)return ans; ans=min(ans,query(1,1,n)); return ans;}int main(){ int q,x,y,z; read(n),read(m); for(ri i=1;i<=m;i++){ read(x),read(y),read(z); edge[i]=Edge(x,y,z); } kruskal(); for(ri i=1;i<=n;i++){//不一定联通 if(!dfn[i]){ dep[i]=1,fa[i]=0; dfs_1(i); dfs_2(i,i); } } build(1,1,n); read(q); while(q--){ read(x),read(y); int tmp=query_path(x,y); if(!tmp)puts("-1"); else printf("%d\n",tmp); } return 0;}