直接点权下放到边权，每次查询从dfs序的st[u]+1,ed[v]之间查询，
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define lson rt<<1 #define rson rt<<1|1 using namespace std; const int maxx = 2e5+6; const int INF = 2e9; struct node{ int l,r; int w; }tree[maxx<<2]; int head[maxx],edge[maxx],Next[maxx],ver[maxx],dis[maxx]; int a[maxx],siz[maxx],top[maxx],son[maxx],d[maxx],fa[maxx],id[maxx],rk[maxx]; int p[maxx],pw[maxx],dfn[maxx]; int n,m,tot,uu,vv,cnt,q; void add(int x,int y,int w){ ver[++tot]=y;edge[tot]=w;Next[tot]=head[x];head[x]=tot; ver[++tot]=x;edge[tot]=w;Next[tot]=head[y];head[y]=tot; } void dfs1(int u,int f,int depth) { d[u]=depth; fa[u]=f; siz[u]=1; for (int i=head[u];i;i=Next[i]){ int v=ver[i]; if (v==f)continue; dis[v]=edge[i]; dfs1(v,u,depth+1); siz[u]+=siz[v]; if (siz[v]>siz[son[u]]) son[u]=v; } } void dfs2(int u,int t) { top[u]=t; id[u]=++cnt; dfn[cnt]=u; if (!son[u]) return ; dfs2(son[u],t); for (int i=head[u];i;i=Next[i]) { int v=ver[i]; if (v!=son[u] && v!=fa[u]) dfs2(v,v); } } void buildtree(int rt,int l,int r){ tree[rt].l=l; tree[rt].r=r; if (l==r){ tree[rt].w=dis[dfn[l]]; return ; } int mid=(l+r)>>1; buildtree(lson,l,mid); buildtree(rson,mid+1,r); tree[rt].w=min(tree[lson].w,tree[rson].w); } int query(int rt,int ql,int qr){ if (ql>qr)return INF; int l=tree[rt].l; int r=tree[rt].r; if (ql<=l && r<=qr){ return tree[rt].w; } int mid=(l+r)>>1; if (qr<=mid){ return query(lson,ql,qr); }else if (ql>mid){ return query(rson,ql,qr); }else { return min(query(lson,ql,qr),query(rson,ql,qr)); } } int qRange(int x,int y){ int ans=INF; while(top[x]!=top[y]){ if (d[top[x]]<d[top[y]])swap(x,y); ans=min(ans,query(1,id[top[x]],id[x])); x=fa[top[x]]; } if (d[x]>d[y])swap(x,y); ans=min(ans,query(1,id[x]+1,id[y])); return ans; } int main(){ int st; while(~scanf("%d%d",&n,&q)){ tot=0; cnt=0; memset(head,0,sizeof(head)); memset(tree,0,sizeof(tree)); for (int i=1;i<=n;i++){ scanf("%d%d",&p[i],&pw[i]); if (p[i]==0 && pw[i]==0){ st=i; }else { add(i,p[i],pw[i]); } } dfs1(st,0,1); dis[st]=INF; dfs2(st,st); buildtree(1,1,cnt); while(q--){ scanf("%d%d",&uu,&vv); printf("%d ",qRange(uu,vv)); } } return 0; }