解决图中：
- 任意两节点（可以不连通）找到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
",val[lca(x,y)]);
}
return 0;
}