一道：LCA+最大生成树
个人认为把这两个的板子写好（并熟练掌握了之后）就没什么难的
（但我还是de了好久bug）qwq
最大生成树：其实就是最小生成树的变形
我用的是kruskal
（个人觉得kruskal比较好像and好写）
所以
对于kruskal而言
只是把边从小到大排序改成从大到小序就可以了
需要多维护一个w[ i ][ j ]数组
用来存从i点向上走j^2次步这个过程中最大承重量
透
又是数组开小了
（明明我算的不用那么大的啊qwq）
向现实低头
#include#include #define INF 999999999using namespace std;inline int read()//快读 { int sum = 0,p = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') p = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (sum *= 10)+= ch - '0'; ch = getchar(); } return sum * p;}const int maxn = 10005,maxm = 50005;int n,m,cnt;int head[maxn],deep[maxn],f[maxn][25],fa[maxn],w[maxn][21];bool vis[maxn];struct edge1{ int from,to,wei;}e1[maxm];struct edge2{ int next,to,wei;}e2[maxm*2];bool cmp(edge1 a,edge1 b){ return a.wei > b.wei;}int find(int o){ if(o == fa[o]) return o; else return fa[o] = find(fa[o]);}void add(int x,int y,int z){ e2[++cnt].next = head[x]; e2[cnt].to = y; e2[cnt].wei = z; head[x] = cnt;}void kruskal(){ sort(e1+1,e1+m+1,cmp); for(int i = 1;i <= n;i++) fa[i] = i;//并查集初始化：每个节点各为一个子树，即每个点的父节点都是他自己 int v,u; for(int i = 1;i <= m;i++) { u = find(e1[i].from); v = find(e1[i].to); if(u == v)//如果两个点已经在一个图中了，即这两个点已经有一个最大的边加入到生成树中了，那么再加进去就会生成环，所以不能加 continue; fa[u] = v;//把v加入到生成树中 add(e1[i].from,e1[i].to,e1[i].wei); add(e1[i].to,e1[i].from,e1[i].wei);//无向图，双向加边 } return;}void dfs(int o){ vis[o] = true; for(int i = head[o];i;i = e2[i].next) { int to = e2[i].to; if(vis[to]) continue; deep[to] = deep[o] + 1; f[to][0] = o; w[to][0] = e2[i].wei; dfs(to); }} int lca(int x,int y){ if(find(x) != find (y)) return -1; int ans = INF; if(deep[x] > deep[y]) swap(x,y); for(int i = 20;i >= 0;i--) if(deep[f[y][i]] >= deep[x]) { ans = min(ans,w[y][i]); y = f[y][i]; } if(x == y) return ans; for(int i = 20;i>=0;i--) if(f[x][i] != f[y][i]) { ans = min(ans,min(w[x][i],w[y][i])); x = f[x][i]; y = f[y][i]; } ans = min(ans,min(w[x][0], w[y][0])); return ans;}int main(){ n = read(),m = read(); int x,y,z; for(int i = 1;i <= m;i++) { x = read(),y = read(),z = read(); e1[i].from = x; e1[i].to = y; e1[i].wei = z; } kruskal(); for(int i = 1;i <= n;i++) if(!vis[i]) { deep[i] = 1; dfs(i); f[i][0] = i; w[i][0] = INF; } for(int i = 1;i <= 20;i++) for(int j = 1;j <= n;j++) { f[j][i]=f[f[j][i-1]][i-1]; w[j][i]=min(w[j][i-1], w[f[j][i-1]][i-1]); } int q = read(); for(int i = 1;i <= q;i++) { x = read(),y = read(); printf("%d\n",lca(x,y)); } return 0;}