ICPC 2017 Latin American Regional I（LCA）

[题目连接](https://vjudge.net/problem/Gym-101889I) ------------ 求出图的最小生成树 在树上每次求两点的公共祖先的同时，倍增求出两点简单路径的边权最大值 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=4e5+5; int n,m,fa[M],mst,dep,head[M],nxt[M],ver[M],edge[M],tot,d[M],f[M][20],mx[M][20]; struct road { int u,v,w; bool operator <(const road& a)const{return w<a.w;} }path[M]; map<pair<int,int>,int> mp; queue<int> q; int fnd(int x){return fa[x]==x?x:fa[x]=fnd(fa[x]);} void add(int x,int y,int z) { nxt[++tot]=head[x]; head[x]=tot; ver[tot]=y; edge[tot]=z; } void kruskal() { sort(path+1,path+1+m); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++) { int t1=fnd(path[i].u); int t2=fnd(path[i].v); if(t1!=t2) { mst+=path[i].w; fa[t1]=t2; add(path[i].u,path[i].v,path[i].w); add(path[i].v,path[i].u,path[i].w); } } } void bfs() { d[1]=1; q.push(1); while(!q.empty()) { int x=q.front();q.pop(); for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(d[y])continue; d[y]=d[x]+1; mx[y][0]=edge[i]; f[y][0]=x; for(int j=1;j<=dep;j++) { f[y][j]=f[f[y][j-1]][j-1]; mx[y][j]=max(mx[y][j-1],mx[f[y][j-1]][j-1]); } q.push(y); } } } int lca(int x,int y) { int res=0; if(d[y]>d[x])swap(x,y); for(int i=dep;i>=0;i--) if(d[f[x][i]]>=d[y])res=max(res,mx[x][i]),x=f[x][i]; if(x==y)return res; for(int i=dep;i>=0;i--) if(f[x][i]!=f[y][i])res=max(res,max(mx[x][i],mx[y][i])),x=f[x][i],y=f[y][i]; return max(res,max(mx[x][0],mx[y][0])); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z;scanf("%d%d%d",&x,&y,&z); path[i]=(road){x,y,z}; mp[make_pair(x,y)]=z; } kruskal(); dep=(int)(log(n)/log(2))+1; bfs(); int q;scanf("%d",&q); while(q--) { int x,y;scanf("%d%d",&x,&y); printf("%d\n",mst+mp[make_pair(x,y)]-lca(x,y)); } return 0; } ```