https://www.luogu.com.cn/problem/P1967
换了一种做法做出来了
不记得老师之前怎么讲的
1 #include<bits/stdc++.h> 2 #define R 200001 3 using namespace std; 4 int n,m,cnt,q; 5 struct node 6 { 7 int u,v,dis; 8 }edge[R]; 9 bool cmp(node a,node b) 10 { 11 return a.dis>b.dis; 12 } 13 struct node2 14 { 15 int v,nxt; 16 }E[R]; 17 int head[R],tmp; 18 int val[R],ff[R],vis[R]; 19 int fa[R],top[R],son[R]; 20 int size[R],dep[R]; 21 void add(int u,int v) 22 { 23 E[++tmp].nxt=head[u]; 24 E[tmp].v=v; 25 head[u]=tmp; 26 } 27 int find(int x) 28 { 29 if(x==ff[x]) return x; 30 else return ff[x]=find(ff[x]); 31 } 32 void dfs1(int u,int pa) 33 { 34 size[u]=1; 35 vis[u]=1; 36 for(int i=head[u];i;i=E[i].nxt) 37 { 38 int v=E[i].v; 39 if(v==pa) continue; 40 dep[v]=dep[u]+1; 41 fa[v]=u; 42 dfs1(v,u); 43 size[u]+=size[v]; 44 if(size[v]>size[son[u]]) son[u]=v; 45 } 46 } 47 void dfs2(int u,int tp) 48 { 49 top[u]=tp; 50 if(son[u]) dfs2(son[u],tp); 51 for(int i=head[u];i;i=E[i].nxt) 52 { 53 int v=E[i].v; 54 if(v==fa[u]||v==son[u]) continue; 55 dfs2(v,v); 56 } 57 } 58 void kruskal() 59 { 60 sort(edge+1,edge+1+m,cmp); 61 for(int i=1;i<=n;i++) ff[i]=i; 62 for(int i=1;i<=m;i++) 63 { 64 int fu=find(edge[i].u),fv=find(edge[i].v); 65 if(fu!=fv) 66 { 67 val[++cnt]=edge[i].dis; 68 ff[cnt]=ff[fu]=ff[fv]=cnt; 69 add(fu,cnt),add(cnt,fu),add(fv,cnt),add(cnt,fv); 70 } 71 } 72 for(int i=1;i<=cnt;i++) 73 { 74 if(!vis[i]) 75 { 76 int f=find(i); 77 dfs1(f,0); 78 dfs2(f,f); 79 } 80 } 81 } 82 int LCA(int u,int v) 83 { 84 while(top[u]!=top[v]) 85 { 86 if(dep[top[u]]>dep[top[v]]) u=fa[top[u]]; 87 else v=fa[top[v]]; 88 } 89 return dep[u]<dep[v]?u:v; 90 } 91 int main() 92 { 93 cin>>n>>m; 94 cnt=n; 95 for(int i=1;i<=m;i++) cin>>edge[i].u>>edge[i].v>>edge[i].dis; 96 kruskal(); 97 cin>>q; 98 while(q--) 99 { 100 int u,v; 101 cin>>u>>v; 102 if(find(u)!=find(v)) puts("-1"); 103 else cout<<val[LCA(u,v)]<<endl;; 104 } 105 return 0; 106 }