/* 树链刨分+离线操作 题意：给你一棵树，和询问x，y 从节点x--节点1的小于等于y的最大值. 解：先建一个空树，将树的边权值从小到大排序，将询问y按从小到大排序 对于每次询问y将小于等于y的边权值的边增加，在进行询问将结果储存最后输出就可以 易错点：要考虑到节点1到节点1的情况需特判。*/ #pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> using namespace std; #define N 110000 #define inf 0x3fffffff int f[N]; int top[N]; int fa[N]; int siz[N]; int nu,yong; int head[N]; int deep[N]; int son[N]; int w[N]; int Max; struct node { int u,v,w,next,we; } bian[N*4],ff[N],fy[N]; void init() { yong=nu=0; memset(head,-1,sizeof(head)); memset(son,-1,sizeof(son)); } void addedge(int u,int v,int w) { bian[yong].u=u; bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } void dfs(int u,int father,int d) { deep[u]=d; fa[u]=father; siz[u]=1; int i; for(i=head[u]; i!=-1; i=bian[i].next) { int v=bian[i].v; if(v!=father) { dfs(v,u,d+1); siz[u]+=siz[v]; if(son[u]==-1||siz[son[u]]<siz[v]) son[u]=v; } } return ; } void getnu(int u,int cnt) { f[u]=nu++; top[u]=cnt; if(son[u]==-1)return ; getnu(son[u],cnt); int i; for(i=head[u]; i!=-1; i=bian[i].next) { int v=bian[i].v; if(v!=son[u]&&v!=fa[u]) getnu(v,v); } return ; } int cmp(const void *a,const void *b) { return (*(struct node *)a).v-(*(struct node *)b).v; } int cmpp(const void *a,const void *b) { return (*(struct node *)a).w-(*(struct node *)b).w; } struct nodee { int l,r,maxx; } tree[N*4]; int Ma(int v,int vv) { return v>vv?v:vv; } void pushup(int t) { tree[t].maxx=Ma(tree[t*2].maxx,tree[t*2+1].maxx); } void build(int t,int l,int r) { tree[t].l=l; tree[t].r=r; if(tree[t].l==tree[t].r) { tree[t].maxx=-1; return ; } int mid=(tree[t].l+tree[t].r)/2; build(t*2,l,mid); build(t*2+1,mid+1,r); pushup(t); } void update(int t,int x,int y) { if(tree[t].l==x&&tree[t].r==x) { tree[t].maxx=y; return ; } int mid=(tree[t].l+tree[t].r)/2; if(x<=mid)update(t*2,x,y); else update(t*2+1,x,y); pushup(t); } void qury(int t,int l,int r) { if(tree[t].l==l&&tree[t].r==r) { Max=Ma(Max,tree[t].maxx); return ; } int mid=(tree[t].l+tree[t].r)/2; if(r<=mid)qury(t*2,l,r); else if(l>mid)qury(t*2+1,l,r); else { qury(t*2,l,mid); qury(t*2+1,mid+1,r); } pushup(t); } int findmax(int u,int v) { if(u==v)return -1;//特判由于可能出现节点1到节点1的情况是不存在的 int f1=top[u]; int f2=top[v]; int ans=-inf; while(f1!=f2) { if(deep[f1]<deep[f2]) { swap(f1,f2); swap(u,v); } Max=-inf; qury(1,f[f1],f[u]); ans=Ma(ans,Max); u=fa[f1]; f1=top[u]; } if(u==v)return ans; if(deep[u]>deep[v]) swap(u,v); Max=-inf; qury(1,f[son[u]],f[v]); ans=Ma(ans,Max); return ans; } int main() { int n,i,j,k,t; scanf("%d",&t); while(t--) { scanf("%d",&n); init(); for(i=1; i<n; i++) { scanf("%d%d%d",&ff[i].u,&ff[i].v,&ff[i].w); addedge(ff[i].u,ff[i].v,ff[i].w); addedge(ff[i].v,ff[i].u,ff[i].w); } dfs(1,1,0);//得到deep。fa,siz，son数组值 getnu(1,1);//得到f，top的值 for(i=1; i<n; i++) { if(deep[ff[i].u]<deep[ff[i].v]) swap(ff[i].u,ff[i].v); w[ff[i].u]=ff[i].w; } build(1,1,nu-1);//建空树 scanf("%d",&k); for(i=1; i<=k; i++) { scanf("%d%d",&fy[i].u,&fy[i].v); fy[i].w=i;//记录下标 } qsort(fy+1,k,sizeof(fy[0]),cmp);//排序 qsort(ff+1,n-1,sizeof(ff[0]),cmpp); for(i=1,j=1; i<=k; i++) { for(; j<n;) { if(fy[i].v>=ff[j].w) update(1,f[ff[j].u],ff[j].w);//加边 else break; j++; } fy[i].we=findmax(1,fy[i].u);//查找 } qsort(fy+1,k,sizeof(fy[0]),cmpp);//再次按下标排序 for(i=1; i<=k; i++)//输出 printf("%d ",fy[i].we); } return 0; }