链接:https://nanti.jisuanke.com/t/38229
题意:
给一棵树,多次查询,每次查询两点之间权值<=k的边个数
题解:
离线询问,树链剖分后bit维护有贡献的位置即可
#include <bits/stdc++.h>
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
using namespace std;
const int maxn=2e5+10,maxm=2e6+10;
int n,m;
#define tpyeinput int
inline bool read(tpyeinput &num){int flag=1,ch=getchar();if(ch==EOF) return false;num=0;while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=num*10+ch-'0',ch=getchar();}num*=flag;return true;}
inline bool read(tpyeinput &num1,tpyeinput &num2){return read(num1)&&read(num2);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3){return read(num1)&&read(num2)&&read(num3);}
inline bool read(tpyeinput &num1,tpyeinput &num2,tpyeinput &num3,tpyeinput &num4){return read(num1)&&read(num2)&&read(num3)&&read(num4);}
struct node{int from,to,cost,next;}e[maxn<<1],e2[maxn];
int head[maxn],nume,cnt2;
inline void add(int a,int b,int c){e[++nume]={a,b,c,head[a]};head[a]=nume;}
int fa[maxn],sz[maxn],top[maxn],remp[maxn],ans[maxn];
int son[maxn],in[maxn],cnt,deep[maxn];
void dfs1(int now,int pre,int d){
deep[now]=d;sz[now]=1;fa[now]=pre;
for(int i=head[now];i;i=e[i].next){
if(e[i].to==pre) continue;
dfs1(e[i].to,now,d+1);
sz[now]+=sz[e[i].to];
if(sz[son[now]]<sz[e[i].to]) son[now]=e[i].to;
}
}
void dfs2(int now,int pre,int st){
top[now]=st;in[now]=++cnt;remp[cnt]=now;
if(son[now]) dfs2(son[now],now,st);
for(int i=head[now];i;i=e[i].next)
if(e[i].to!=pre&&e[i].to!=son[now]) dfs2(e[i].to,now,e[i].to);
}
struct data{int l,r,val,id;}ask[maxn];
int cmp(node a,node b){return a.cost<b.cost;}
int cmp2(data a,data b){return a.val<b.val;}
struct bit{
int node[maxn];
inline int lb(int x) {return x&(-x);}
void update(int pos){for(int i=pos;i<=n;i+=lb(i))node[i]++;}
int ask(int pos){int sum=0; for(int i=pos;i;i-=lb(i))sum+=node[i];return sum;}
inline int query(int l,int r){return ask(r)-ask(l-1);}
}tree;
int query(int a,int b){
int sum=0;
while(top[a]!=top[b]){
if(deep[top[a]]<deep[top[b]]) swap(a,b);
sum+=tree.query(in[top[a]],in[a]);
a=fa[top[a]];
}
if(a==b)return sum;
if(deep[a]>deep[b]) swap(a,b);
sum+=tree.query(in[son[a]],in[b]);
return sum;
}
int main() {
read(n,m);
rep(i,2,n) {int a,b,c;read(a,b,c);add(a,b,c);e2[++cnt2]=e[nume];add(b,a,c);}
sort(e2+1,e2+1+cnt2,cmp);
rep(i,1,m) {ask[i].id=i;read(ask[i].l,ask[i].r,ask[i].val);}
sort(ask+1,ask+1+m,cmp2);
dfs1(1,1,0);dfs2(1,1,1);
int pos=1;
rep(i,1,m){
while(pos<=cnt2&&e2[pos].cost<=ask[i].val) {
int x=e2[pos].to;
if(deep[e2[pos].from]>deep[e2[pos].to]) x=e2[pos].from;
tree.update(in[x]); pos++;
}
ans[ask[i].id]=query(ask[i].l,ask[i].r);
}
rep(i,1,m) printf("%d\n",ans[i]);
}