感觉这题挺水的……真的挺水的……
原题：
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
0 < n < 10,000，0 < m < 50,000，0 < q < 30,000，0 ≤ z ≤ 100,000。
思路非常简单，求最大生成树，然后剖，甚至连修改操作都没有
这题水啊，二分就有60，正解就是个裸的生成树+剖
如果NOIP考自己学过的比较高级的高级数据结构是一件挺好的事，受到NOIP难度的限制，考比较高级的东西的话就会裸得多，就没有呢么多魔性的东西了（然而因为选手水平提升而难度增加的概率非常大QAQ）
有几点需要注意的地方，因为这里要用点的权值当边的权值，所以在路径遇到拐点（就是deep[x]>deep[y]<deep[z]）的时候要特判一下，首先如果最后到一条重链上的时候x和y一样的话就不找了，因为这个点就是拐点，查找的话结果会是拐点和它的父节点之间的边，就跟路径没关系了，如果查找的话，查找左端点要是深度比较浅的内个点的标号+1，因为深度比较浅的内个点的值是它和它父节点之间连的边的值，但是在往同一个重链上攀的时候就不用这么判断了，因为不+1的话刚好把重链顶点和它的父节点之间的边算上了，就不用再算一遍了
第一次写成树剖，这个东西终于懂了QAQ，收货还是挺多的
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int read(){int z=,mark=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mark=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mark;
}
struct ddd{int next,y,value;}e[];int LINK[],ltop=;
inline void insert(int x,int y,int z){e[++ltop].next=LINK[x];LINK[x]=ltop;e[ltop].y=y;e[ltop].value=z;}
struct ccc{int x,y,value;}tu[];int tltop=;
inline void insert_tu(int x,int y,int z){tu[++tltop].x=x,tu[tltop].y=y,tu[tltop].value=z;}
struct dcd{int sleft,sright,mid,svalue;}tree[];
int n,m;
int size[],deep[],father[],big_child[],top[];
int dfs_xv[],fan_xv[],cnt=,b_value[];
int ji[];
int group[],gtop=;
int cha(int x){ if(ji[x]==x) return x; ji[x]=cha(ji[x]); return ji[x];}
void bing(int x,int y){ int ji_x=cha(x),ji_y=cha(y); ji[ji_x]=ji_y;}
bool compare(ccc x,ccc y){ return x.value>y.value;}//这里求的是最大生成树
void kruskal(){
for(int i=;i<=n;i++) ji[i]=i;
sort(tu+,tu+tltop+,compare);
int _cnt=;
for(int i=;i<=tltop;i++){
int _x=cha(tu[i].x),_y=cha(tu[i].y);
if(_x!=_y){
bing(_x,_y);
insert(tu[i].x,tu[i].y,tu[i].value),insert(tu[i].y,tu[i].x,tu[i].value);
if(++_cnt==n-) return ;
}
}
}
void dfs1(int x,int _deep,int _father){
group[x]=gtop;
father[x]=_father,deep[x]=_deep,size[x]=;
int max_size=,max_child=;
for(int i=LINK[x];i;i=e[i].next)if(e[i].y!=_father){
dfs1(e[i].y,_deep+,x);
b_value[e[i].y]=e[i].value;
size[x]+=size[e[i].y];
if(size[e[i].y]>max_size){ max_size=size[e[i].y]; max_child=e[i].y;}
}
big_child[x]=max_child;
}
void dfs2(int x,int _top){
top[x]=_top; dfs_xv[++cnt]=x; fan_xv[x]=cnt;
if(big_child[x]) dfs2(big_child[x],_top);
for(int i=LINK[x];i;i=e[i].next)if(e[i].y!=father[x] && e[i].y!=big_child[x])
dfs2(e[i].y,e[i].y);
}
void get_SegmentTree(int x,int _left,int _right){
tree[x].sleft=_left,tree[x].sright=_right,tree[x].mid=(_left+_right)>>;
if(_left==_right) tree[x].svalue=b_value[dfs_xv[_left]];//注意这里
else{
get_SegmentTree(x<<,_left,tree[x].mid),get_SegmentTree(x<<|,tree[x].mid+,_right);
tree[x].svalue=min(tree[x<<].svalue,tree[x<<|].svalue);
}
}
int search(int x,int _left,int _right){
if(tree[x].sleft==_left && tree[x].sright==_right) return tree[x].svalue;
else if(_left<=tree[x].mid && _right>tree[x].mid) return min(search(x<<,_left,tree[x].mid),search(x<<|,tree[x].mid+,_right));
else if(_right<=tree[x].mid) return search(x<<,_left,_right);
else return search(x<<|,_left,_right);
}
int pa(int x,int y){
int minn=;
int fa=top[x],fb=top[y];
while(fa!=fb){
if(deep[fa]<deep[fb]) swap(fa,fb),swap(x,y);
minn=min(minn,search(,fan_xv[fa],fan_xv[x]));//注意这里是x
x=father[fa]; fa=top[x];
}
if(deep[x]>deep[y]) swap(x,y);
if(x!=y) minn=min(minn,search(,fan_xv[x]+,fan_xv[y]));//注意，如果不加判断会把拐点和拐点的父节点之间的连边也算进去,而且注意+1
return minn;
}
int main(){//freopen("ddd.in","r",stdin); freopen("ddd.out","w",stdout);
memset(group,,sizeof(group));
cin>>n>>m;
int _left,_right,_value;
while(m --> ){//趋向于
_left=read(),_right=read(),_value=read();
insert_tu(_left,_right,_value);
}
kruskal();
for(int i=;i<=n;i++)if(!group[i]){ b_value[i]=; gtop++,dfs1(i,,),dfs2(i,i);}//注意连通图问题
get_SegmentTree(,,n);
cin>>m;
/*for(int i=1;i<=n;i++) cout<<b_value[i]<<" ";
cout<<endl;
for(int i=1;i<=n;i++) cout<<father[i]<<' ';
cout<<endl;*/
while(m --> ){//趋向于
_left=read(),_right=read();
if(group[_left]==group[_right]) printf("%d\n",pa(_left,_right));
else printf("-1\n");
}
return ;
}