分析
我们知道答案一定再最小生成树上
于是我们按边权从小到大建立 kruskal 重构树
然后每次查询 lca 的值即可
由于询问较多采用 st 表维护 lca
代码
格式化代码
- #include<bits/stdc++.h>
- using namespace std;
- const int mod = 1e9+7;
- struct node {
- int x,y,z;
- };
- node d[400100];
- vectorv[400100];
- int lg[400100],A,B,C,P,dep[400100],no[400100];
- int pr[400100][23],val[400100],cnt,n,m,q,T,fa[400100];
- inline int rnd(){return A=(A*B+C)%P;}
- inline int mmin(int x,int y){return dep[x]<dep[y]?x:y;}
- inline int sf(int x){return fa[x]==x?x:fa[x]=sf(fa[x]);}
- inline bool cmp(const node x,const node y){return x.z<y.z;}
- inline int que(int x,int y){int k=lg[y-x+1];return mmin(pr[x][k],pr[y-(1<<k)+1][k]);}
- inline void dfs(int x,int f){
- dep[x]=dep[f]+1;
- pr[++T][0]=x;
- no[x]=T;
- for(int i=0;i<v[x].size();++i){
- dfs(v[x][i],x);
- pr[++T][0]=x;
- }
- }
- inline int ra(){
- int x=0;char s=getchar();
- while(!isdigit(s))s=getchar();
- while(isdigit(s))x=(x<<1)+(x<<3)+(s-'0'),s=getchar();
- return x;
- }
- int main(){
- int i,j,k,Ans=0;
- n=ra(),m=ra();
- for(i=1;i<=m;++i)d[i].x=ra(),d[i].y=ra(),d[i].z=ra();
- sort(d+1,d+m+1,cmp);
- for(i=1;i<=2*n;++i)fa[i]=i;
- k=0,cnt=n;
- for(i=1;i<=m;++i){
- int x=d[i].x,y=d[i].y;
来源: http://www.bubuko.com/infodetail-3204081.html