给出一个图，询问图上两点间路径上最小边权的最大值。
先跑一次最大生成树。
树剖维护路径最小边权。
树剖又双叒叕写挂了。
1 #include<cstring> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 #include<cctype> 6 #define foru(i,x,y) for(int i=x;i<=y;i++) 7 #define mm(a) memset(a,0,sizeof(a)) 8 #define ford(i,x,y) for(int i=x;i>=y;i--) 9 #define re(x) x=read() 10 using namespace std; 11 typedef long long LL; 12 typedef double db; 13 const int inf=1e9; 14 const int N=2e5+10; 15 16 struct dat{int f,t,w;}a[N],b[N]; 17 struct edge{int to,nxt,w;}e[N]; 18 int head[N],top[N],f[N],F[N],siz[N],t[N*20],son[N],d[N],id[N],ne,nb,n,m,cnt; 19 20 int read(){ 21 static int f,x;static char ch; 22 x=f=0;ch=getchar(); 23 while(!isdigit(ch)){f=(ch=='-');ch=getchar();} 24 while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();} 25 return f?-x:x; 26 } 27 28 bool cmp(dat a,dat b){ 29 return a.w>b.w; 30 } 31 32 int gf(int a){ 33 if(a==F[a])return a; 34 return F[a]=gf(F[a]); 35 } 36 37 void add(int a,int b,int c){ 38 e[++ne]=(edge){b,head[a],c};head[a]=ne; 39 e[++ne]=(edge){a,head[b],c};head[b]=ne; 40 } 41 42 void dfs(int k,int fa){ 43 f[k]=fa;siz[k]=1; 44 for(int i=head[k];i;i=e[i].nxt){ 45 int v=e[i].to; 46 if(v==fa)continue; 47 d[v]=d[k]+1; 48 dfs(v,k); 49 siz[k]+=siz[v]; 50 if(siz[v]>siz[son[k]])son[k]=v; 51 } 52 } 53 54 void build(int k,int tp){ 55 id[k]=++cnt;top[k]=tp; 56 if(son[k])build(son[k],tp); 57 for(int i=head[k];i;i=e[i].nxt){ 58 int v=e[i].to; 59 if(v==f[k])continue; 60 if(v!=son[k])build(v,v); 61 } 62 } 63 64 #define mid ((L+R)>>1) 65 #define ls (k<<1) 66 #define rs (k<<1|1) 67 68 void upd(int k,int L,int R,int p,int x){ 69 if(p<L||p>R)return; 70 if(L==R){t[k]=x;return;} 71 upd(ls,L,mid,p,x);upd(rs,mid+1,R,p,x); 72 t[k]=min(t[ls],t[rs]); 73 } 74 75 int quiry(int k,int L,int R,int l,int r){ 76 if(r<L||l>R)return inf; 77 if(l<=L&&R<=r)return t[k]; 78 return min(quiry(ls,L,mid,l,r),quiry(rs,mid+1,R,l,r)); 79 } 80 81 int find(int a,int b){ 82 int ret=inf; 83 while(top[a]!=top[b]){ 84 if(d[top[a]]<d[top[b]])swap(a,b); 85 //又写成了(d[a]<d[b]) 86 int tmp=quiry(1,1,cnt,id[top[a]],id[a]); 87 ret=min(ret,tmp); 88 a=f[top[a]]; 89 } 90 if(d[a]<d[b])swap(a,b); 91 if(a!=b)ret=min(ret,quiry(1,1,cnt,id[b]+1,id[a])); 92 return ret; 93 } 94 95 int main(){ 96 scanf("%d%d",&n,&m); 97 foru(i,1,m){re(a[i].f);re(a[i].t);re(a[i].w);F[i]=i;} 98 sort(a+1,a+1+m,cmp); 99 foru(i,1,m){ 100 int f1=gf(a[i].f),f2=gf(a[i].t); 101 if(f1!=f2){ 102 F[f2]=f1; 103 add(a[i].f,a[i].t,a[i].w); 104 b[++nb]=a[i]; 105 } 106 } 107 mm(f);m=n-1; 108 dfs(1,0); 109 build(1,1); 110 foru(i,1,cnt)upd(1,1,cnt,i,inf); 111 foru(i,1,nb){ 112 if(d[b[i].f]<d[b[i].t])swap(b[i].f,b[i].t); 113 upd(1,1,cnt,id[b[i].f],b[i].w); 114 } 115 int q=read(),u,v; 116 while(q--){ 117 re(u);re(v); 118 if(gf(u)!=gf(v)){puts("-1");continue;} 119 printf("%d ",find(u,v)); 120 } 121 return 0; 122 }