链接：https://www.jisuanke.com/contest/2290/challenges 题意：给定一棵树每条边都带有权值，给定 m 个询问查询 u 和 v 的路径上权值小于等于 w 的边的个数 思路：先拆点将边权变为点权，可以离线来做。将点权小于当前询问权值的点，更新到线段树上，然后在查询路径上出现过的点的数量。（大于询问权值的点，还没更新上去）
#include <bits/stdc++.h> #define ll long long #define ls (rt<<1) #define rs (rt<<1|1) using namespace std; const int maxn=2e5+10,mod=1e9+7; int head[maxn],cnt; struct Edge { int nxt,to; }edges[maxn<<1]; void add(int u,int v) { edges[++cnt].nxt=head[u]; edges[cnt].to=v; head[u]=cnt; } struct Opt { int u,v,w,id; bool operator<(const Opt& b) const { return w<b.w; } }e[maxn],opt[maxn]; int n,m; int num[maxn],depth[maxn],fa[maxn],son[maxn]; int start[maxn],top[maxn],times; int st[maxn<<2]; void dfs1(int u) { num[u]=1; for(int i=head[u];i!=-1;i=edges[i].nxt) { int v=edges[i].to; if(v==fa[u]) continue; depth[v]=depth[u]+1; fa[v]=u; dfs1(v); num[u]+=num[v]; if(num[v]>num[son[u]]) son[u]=v; } } void dfs2(int u,int x) { start[u]=++times; top[u]=x; if(!son[u]) return; dfs2(son[u],x); for(int i=head[u];i!=-1;i=edges[i].nxt) { int v=edges[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } void update(int rt,int p,int L,int R) { if(L==R) { st[rt]++; return; } int mid=(L+R)>>1; if(p<=mid) update(ls,p,L,mid); if(p>mid) update(rs,p,mid+1,R); st[rt]=st[ls]+st[rs]; } int query(int rt,int l,int r,int L,int R) { if(l<=L&&R<=r) return st[rt]; int mid=(L+R)>>1; int ans=0; if(l<=mid) ans+=query(ls,l,r,L,mid); if(r>mid) ans+=query(rs,l,r,mid+1,R); return ans; } int qPath(int u,int v) { int ans=0; while(top[u]!=top[v]) { if(depth[top[u]]<depth[top[v]]) swap(u,v); ans+=query(1,start[top[u]],start[u],1,n); u=fa[top[u]]; } if(depth[u]>depth[v]) swap(u,v); ans+=query(1,start[u],start[v],1,n); return ans; } int ans[maxn]; int main() { scanf("%d%d",&n,&m); cnt=-1,memset(head,-1,sizeof(head)); int tot=n; int u,v,w; for(int i=1;i<=n-1;++i) { scanf("%d%d%d",&u,&v,&w); tot++; add(u,tot),add(tot,v); add(v,tot),add(tot,u); e[i]={u,v,w,tot}; } for(int i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); opt[i]={u,v,w,i}; } sort(e+1,e+1+n-1); sort(opt+1,opt+1+m); int nn=n-1; n=tot; dfs1(1); dfs2(1,1); int p=1; for(int i=1;i<=m;++i) { while(p<=nn&&e[p].w<=opt[i].w) update(1,start[e[p].id],1,n),p++; ans[opt[i].id]=qPath(opt[i].u,opt[i].v); } for(int i=1;i<=m;++i) printf("%d\n",ans[i]); return 0; }也可以用树剖+主席树来做，边权下推成点权。将按DFS序访问到的权值，更新到主席树上，对于每次询问 u，v，可以得到很多重链： t o p [ u ] top[u] top[u] 和 u u u，它们对应的时间序为 s t a r t [ t o p [ u ] ] start[top[u]] start[top[u]] 和 s t a r t [ u ] start[u] start[u] ，也就对应主席树两个版本 s t a r t [ t o p [ u ] ] − 1 start[top[u]]-1 start[top[u]]−1 和 s t a r t [ u ] start[u] start[u]，在这两个版本之间查询找 小于等于 k 的数即可。
当 u 和 v 在同一条重链上时，需要注意的是，访问的是 s t a r t [ u ] start[u] start[u] 和 s t a r t [ v ] start[v] start[v]这两个版本（假设 d e p t h [ u ] < d e p t h [ v ] depth[u]<depth[v] depth[u]<depth[v]），而不是 s t a r t [ u ] − 1 start[u]-1 start[u]−1 和 s t a r t [ v ] start[v] start[v]，因为 u 的点权来自它和父节点的边权，不在这条路径中。 #include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; int head[maxn],cnt; struct Edge { int nxt,to,w; }edges[maxn<<1]; void add(int u,int v,int w) { edges[++cnt].to=v; edges[cnt].nxt=head[u]; edges[cnt].w=w; head[u]=cnt; } struct Opt { int u,v,w; }opt[maxn]; int n,m; vector<int> allw; int total,wt[maxn],ww[maxn]; int depth[maxn],num[maxn],fa[maxn],son[maxn]; int start[maxn],top[maxn],times; int st[maxn*40],root[maxn],ls[maxn*40],rs[maxn*40],no; void dfs1(int u) { num[u]=1; for(int i=head[u];i!=-1;i=edges[i].nxt) { int v=edges[i].to,w=edges[i].w; if(v==fa[u]) continue; depth[v]=depth[u]+1; fa[v]=u; ww[v]=w; dfs1(v); num[u]+=num[v]; if(num[v]>num[son[u]]) son[u]=v; } } void dfs2(int u,int x) { start[u]=++times; wt[times]=ww[u]; top[u]=x; if(!son[u]) return; dfs2(son[u],x); for(int i=head[u];i!=-1;i=edges[i].nxt) { int v=edges[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } int build(int L,int R) { int rt=++no; if(L==R) return rt; int mid=(L+R)>>1; ls[rt]=build(L,mid); rs[rt]=build(mid+1,R); } int update(int pre,int L,int R,int p) { int rt=++no; st[rt]=st[pre]+1; ls[rt]=ls[pre]; rs[rt]=rs[pre]; if(L==R) return rt; int mid=(L+R)>>1; if(p<=mid) ls[rt]=update(ls[pre],L,mid,p); if(p>mid) rs[rt]=update(rs[pre],mid+1,R,p); return rt; } int query(int pre,int now,int l,int r,int L,int R) { if(l<=L&&R<=r) return st[now]-st[pre]; int mid=(L+R)>>1; int ans=0; if(l<=mid) ans+=query(ls[pre],ls[now],l,r,L,mid); if(r>mid) ans+=query(rs[pre],rs[now],l,r,mid+1,R); return ans; } int qPath(int u,int v,int p) { int ans=0; while(top[u]!=top[v]) { if(depth[top[u]]<depth[top[v]]) swap(u,v); ans+=query(root[start[top[u]]-1],root[start[u]],1,p,1,total); u=fa[top[u]]; } if(depth[u]>depth[v]) swap(u,v); ans+=query(root[start[u]],root[start[v]],1,p,1,total); return ans; } int main() { memset(head,-1,sizeof(head)); cnt=0; scanf("%d%d",&n,&m); int u,v,w; for(int i=1;i<=n-1;++i) { scanf("%d%d%d",&u,&v,&w); add(u,v,w),add(v,u,w); allw.push_back(w); } for(int i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); opt[i]={u,v,w}; allw.push_back(w); } sort(allw.begin(),allw.end()); allw.resize(unique(allw.begin(),allw.end())-allw.begin()); dfs1(1); dfs2(1,1); total=allw.size(); root[0]=build(1,total); for(int i=1;i<=n;++i) { int p=lower_bound(allw.begin(),allw.end(),wt[i])-allw.begin()+1; root[i]=update(root[i-1],1,total,p); /* cout<<"p: "<<p<<"\n"; for(int j=1;j<=total;++j) printf("%d ",query(root[0],root[i],j,j,1,total)); puts(""); */ } for(int i=1;i<=m;++i) { int p=lower_bound(allw.begin(),allw.end(),opt[i].w)-allw.begin()+1; printf("%d\n",qPath(opt[i].u,opt[i].v,p)); } return 0; } /* 3 2 1 3 2 1 2 7 2 3 4 2 3 7 */