题意:
给你一棵树，和树上边的权值，在有q组询问a,b，问你从节点a->节点1的路径上，不小于b的最大的边的权值是多少，输出
离线维护最大值线段树即可
模板题
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=1e5+10; int t[N<<2],n,m; void up(int pos) { t[pos]=max(t[pos<<1],t[pos<<1|1]); } void build(int l,int r,int pos) { if(l==r){t[pos]=0;return ;} int m=(l+r)>>1; build(lson);build(rson);up(pos); } void upnode(int x,int v,int l,int r,int pos) { if(l==r){t[pos]=v;return ;} int m=(l+r)>>1; if(x<=m)upnode(x,v,lson); else upnode(x,v,rson); up(pos); } int qmax(int L,int R,int l,int r,int pos) { int ans=-inf; if(L<=l&&r<=R)return t[pos];int m=(l+r)>>1; if(L<=m)ans=max(ans,qmax(L,R,lson)); if(R>m)ans=max(ans,qmax(L,R,rson)); up(pos);return ans; } int id[N],head[N],pos,cnt,top[N],fa[N],son[N],siz[N],dep[N],a,b,c; struct Edge { int to,nex; }edge[N<<1]; void add(int a,int b) { edge[++pos]=Edge{b,head[a]}; head[a]=pos; } void dfs1(int x,int f) { fa[x]=f;dep[x]=dep[f]+1;siz[x]=1;son[x]=0; for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==f)continue; dfs1(v,x); siz[x]+=siz[v]; if(siz[son[x]]<siz[v])son[x]=v; } } void dfs2(int x,int topf) { id[x]=++cnt;top[x]=topf; if(son[x])dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nex) { int v=edge[i].to; if(v==son[x]||v==fa[x])continue; dfs2(v,v); } } int Qmax(int x,int y) { int ans=-inf; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); ans=max(ans,qmax(id[top[x]],id[x],1,n,1)); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); ans=max(ans,qmax(id[x]+1,id[y],1,n,1)); return ans; } void init() { pos=cnt=0;CLR(head,0);dep[1]=siz[0]=0; } struct node { int x,y,id; }s[N]; bool cmp(node a,node b) { return a.y<b.y; } struct Edge2 { int u,v,w; }edge2[N]; bool cmp2(Edge2 a,Edge2 b) { return a.w<b.w; } int ans[N]; int main() { int cas;RI(cas); while(cas--) { RI(n);init(); rep(i,1,n-1) { RIII(edge2[i].u,edge2[i].v,edge2[i].w);add(edge2[i].u,edge2[i].v);add(edge2[i].v,edge2[i].u); } dfs1(1,1);dfs2(1,1);build(1,n,1); RI(m); rep(i,1,m)RII(s[i].x,s[i].y),s[i].id=i; sort(s+1,s+1+m,cmp);sort(edge2+1,edge2+1+n-1,cmp2); int L=1; rep(i,1,m) { while(edge2[L].w<=s[i].y&&L<=n-1 ) { int u=edge2[L].u,v=edge2[L].v; if(dep[u]<dep[v])upnode(id[v],edge2[L].w,1,n,1); else upnode(id[u],edge2[L].w,1,n,1);L++; } ans[s[i].id]=Qmax(1,s[i].x); } rep(i,1,m) printf("%d ",ans[i]==0||ans[i]==-inf?-1:ans[i]); } return 0; }