学了差不多一星期的主席树+树链剖分,再来看这题发现其实是个板子题

一开始想复杂了,以为要用类似求树上第k大的树上差分思想来解决这道题,但其实树链上<=k的元素个数其实直接可以用树链剖分来求

具体是把每条树链放到主席树上询问一下求和就好了

#include<bits/stdc++.h>
using namespace std;
#define maxn 100006
struct Edge{int to,nxt,w;}edge[maxn<<];
int b[maxn],n,m,a[maxn],head[maxn],tot;
void init(){memset(head,-,sizeof head);tot=;}
void addedge(int u,int v,int w){
edge[tot].to=v;edge[tot].nxt=head[u];edge[tot].w=w;head[u]=tot++;
}
struct Node{int lc,rc,sum;}T[maxn*];
int siz,rt[maxn];
int build(int l,int r){
int now=++siz;
T[now].lc=T[now].rc=T[now].sum=;
if(l==r)return now;
int mid=l+r>>;
T[now].lc=build(l,mid);
T[now].rc=build(mid+,r);
return now;
}
int update(int last,int pos,int l,int r){//更新到pos点
int now=++siz;
T[now]=T[last];T[now].sum++;
if(l==r)return now;
int mid=l+r>>;
if(pos<=mid)T[now].lc=update(T[last].lc,pos,l,mid);
else T[now].rc=update(T[last].rc,pos,mid+,r);
return now;
}
int query(int st,int ed,int L,int R,int l,int r){
if(L<=l && R>=r)return T[ed].sum-T[st].sum;
int mid=l+r>>,res=;
if(L<=mid)res+=query(T[st].lc,T[ed].lc,L,R,l,mid);
if(R>mid)res+=query(T[st].rc,T[ed].rc,L,R,mid+,r);
return res;
} int f[maxn],son[maxn],d[maxn],size[maxn];
void dfs1(int x,int pre,int deep){
f[x]=pre;size[x]=;d[x]=deep;
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(y==pre)continue;
a[y]=edge[i].w;
dfs1(y,x,deep+);
size[x]+=size[y];
if(size[y]>size[son[x]])son[x]=y;
}
}
int id[maxn],rk[maxn],idx,top[maxn];
void dfs2(int x,int tp){
top[x]=tp;id[x]=++idx;rk[idx]=x;
if(son[x])dfs2(son[x],tp);
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(y!=son[x] && y!=f[x])dfs2(y,y);
}
} int Query(int x,int y,int pos){
int res=;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]])swap(x,y);
res+=query(rt[id[top[x]]-],rt[id[x]],,pos,,m);
x=f[top[x]];
}
if(id[x]>id[y])swap(x,y);
res+=query(rt[id[x]],rt[id[y]],,pos,,m);
return res;
}
int main(){int q;init();
cin>>n>>q;int u,v,w,k;
for(int i=;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
addedge(u,v,w);addedge(v,u,w);
} a[]=0x3f3f3f3f;
siz=;dfs1(,,);dfs2(,);//树剖
for(int i=;i<=n;i++)b[++m]=a[i];
sort(b+,b++m);
m=unique(b+,b++m)-(b+);
rt[]=build(,m);
for(int i=;i<=idx;i++){
int pos=lower_bound(b+,b++m,a[rk[i]])-b;
rt[i]=update(rt[i-],pos,,m);
} while(q--){
scanf("%d%d%d",&u,&v,&k);
int pos=upper_bound(b+,b++m,k)-(b+);
if(pos==){puts("");continue;}
else cout<<Query(u,v,pos)<<'\n';
}
}

最新文章

  1. 配置mongoDB服务
  2. Unity3d外包(北京)公司(长年承接U3D外包)
  3. guava学习--FluentIterable
  4. VB 进制转换大全
  5. iOS开发——UIWebView
  6. 使用DataList 分页方法
  7. tomcat 系统架构与设计模式 第一部分 系统架构工作原理 转
  8. java_设计模式_装饰者模式_Decorator Pattern(2016-07-28)
  9. 使用jsoup解析html页面内容案例
  10. Redis11种Web应用场景
  11. Java数组练习题小结
  12. J2EE进阶(六)SSH框架工作流程项目整合实例讲解
  13. selenium+java 数据驱动
  14. 《CSAPP》符号和符号表
  15. 第十章&#160;优先级队列 (b4)完全二叉堆:批量建堆
  16. 构造,析构 cpp
  17. WEB前端技巧之JQuery为动态添加的元素绑定事件.md
  18. python ros 使用launch文件启动脚本
  19. Python 编码问题(十四)
  20. Oracle之SQL语句性能优化(34条优化方法)

热门文章

  1. [算法]浅谈求n范围以内的质数(素数)
  2. 洛谷P3719 REXP 题解
  3. MT【328】向量里的最佳逼近
  4. NOT NULL constraint faile(慢就是快,少即是多)
  5. Linux中查看TCP连接数
  6. How to Change Error Message Colors in Windows 10 PowerShell Console
  7. mysql 修改表结构、表字段注释语句
  8. GWAS:拒绝假阳性之case和control数量比例严重失衡的解决方案(SAIGE模型的应用)
  9. Redis实现排行榜功能(实战)
  10. 关于4A系统(我对4A系统的维护的理解)