解决图中：
任意两节点（可以不连通）找到x<->y路径中边权的最小的最大值，反之亦然（也可以用树剖写）给定起点，经过的路径边权有某限制下的（如小于等于某值）点权第k小（大），需要主席树。对于1： 看着像二分。。 对原图边权排序，生成树是直接并查集merge x，y两个节点，重构树的话会新生成一个节点，并把原来的x与y的边断开，用边权当做新节点的点权。
//ff[]是并查集 for(int i=0;i<m;++i){ int fx=find(edge[i].x),fy=find(edge[i].y); if(fx^fy){ ff[fx]=ff[fy]=++id;//id是从n+1开始的 val[id]=edge[i].v; add(id,fx);//id是fx，fy的根，不需要加双向边了 add(id,fy); } }这样做的话最多是2*n-1个节点，原图节点x在新图中还是x，新节点的编号从n+1开始，注意，新节点一定是其子树的根，这也保证了树的深度越小，点权越小。 所以，树建完后，如果原图不连通，则是森林，加上一个虚的根节点，值为-1。 对于需要查询的x，y两点，若他们在原图联通，在新图上一定是某真子树的节点。 因为联通的话一定在同一颗树上，该树的根节点一定是一个新节点，由于根节点的值比子节点小，所以x，y最大路径上的最小边权就是xy的lca，如果排序的时候是从小到大排序的，则lca就是路径中的最大值最小。
luogu P1967 货车运输 每条路径都有限重，求x-y能通过的最重车辆，即求路径中权值最小值的最大值
#include<bits/stdc++.h> using namespace std; #define gc getchar #define TT template<class T>inline TT bool read(T &x){ x=0;register char c=gc();register bool f=0; while(c<48||c>57){if(c==EOF)return 0;f^=c=='-',c=gc();} while(47<c&&c<58)x=(x<<3)+(x<<1)+(c^48),c=gc(); if(f)x=-x;return 1; } TT bool read(T&a,T&b){return read(a)&&read(b);} TT bool read(T&a,T&b,T&c){return read(a)&&read(b)&&read(c);} typedef long long ll; const ll MAXN=1e5+8; int head[MAXN<<1],cnt; int n,m; //原图的边 struct Edge{int x,y,v;bool operator<(const Edge&o){return v>o.v;}}edge[MAXN*5]; //新图的边 struct Node{int y,nt;}node[MAXN<<1]; //新图加边 void add(int x,int y){ node[++cnt].y=y; node[cnt].nt=head[x]; head[x]=cnt; } //lca int deep[MAXN<<1],tot[MAXN<<1],son[MAXN<<1],fa[MAXN<<1]; void dfs1(int x,int f){ deep[x]=deep[f]+1,tot[x]=1,fa[x]=f; int max_son=-1; for(int i=head[x];i;i=node[i].nt){ int y=node[i].y; dfs1(y,x); tot[x]+=tot[y]; if(max_son<tot[y]){ son[x]=y; max_son=tot[y]; } } } int top[MAXN]; void dfs2(int x,int tp){ top[x]=tp; if(son[x])dfs2(son[x],tp); for(int i=head[x];i;i=node[i].nt){ int y=node[i].y; if(top[y])continue; dfs2(y,y); } } //并查集 int ff[MAXN<<1]; int find(int x){return ff[x]^x?ff[x]=find(ff[x]):x;} //新图权值，编号为1~n的权值为0，因为没改动过。。 int val[MAXN<<1],id; void kruskal(){ id=n;//新节点从n+1开始 sort(edge,edge+m); for(int i=0;i<=2*n+1;++i)ff[i]=i; for(int i=0;i<m;++i){ int fx=find(edge[i].x),fy=find(edge[i].y); if(fx^fy){ ff[fx]=ff[fy]=++id; val[id]=edge[i].v; add(id,fx);add(id,fy); } } val[++id]=-1;//原图可能不连通，添加根节点，如果lca是该节点，说明xy不连通。 set<int>root;//森林的根节点 for(int i=1;i<=n;++i){ int f=find(i); if(!root.count(f))root.insert(f); } for(set<int>::iterator it=root.begin();it!=root.end();++it){ add(id,*it);//根节点到森林加边 }//求lca dfs1(id,0); dfs2(id,id); } int lca(int x,int y){ while(top[x]^top[y]){ if(deep[top[x]]>deep[top[y]])x=fa[top[x]]; else y=fa[top[y]]; } return deep[x]<deep[y]?x:y; } int main() { read(n,m); for(int i=0;i<m;++i)read(edge[i].x,edge[i].y,edge[i].v); kruskal(); int q,x,y; read(q); while(q--){ read(x,y); printf("%d\n",val[lca(x,y)]); } return 0; }