LuoguP3066
先吐槽一下,这道题名字好长啊
一个非常明显的思路,利用倍增数组不断向上跳.直到数值大于(L),然后直接差分统计答案就好了.
这种ZROI也考过,不多赘述了.
我们来考虑主席树做法
我们设(d_x)为(x)点到跟的距离
让我们求满足(d_v - d_u<= L,vin Son_u)的(v)的数量
转化一下式子就变成了
(d_v <= d_u + L)
即统计子树内有多少小于等于(d_u+L)的数
我们利用dfs序
将每个子树转化为一个区间
然后利用主席树查询.
注意一个小细节
因为我们的数组经过离散化
因此我们就定位数组中第一个大于(d_u + L)的数,来查询对应区间内有多少数严格小于它就好了
因此在离散化完成数组最后加入一个(infty)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 2e5 + 3;
int L[N],R[N];
struct node{
int sum;
int lc,rc;
}a[N << 5];
struct edge{
int to;
int nxt;
LL data;
}e[N << 1];
LL v[N],b[N];
int rt[N],head[N];
int n,tot = 1,t,cnt;LL g;
inline LL read(){
LL v = 0,c = 1;char ch = getchar();
while(!isdigit(ch)){
if(ch == '-') c = -1;
ch = getchar();
}
while(isdigit(ch)){
v = v * 10 + ch - 48;
ch = getchar();
}
return v * c;
}
inline void add(int x,int y,LL z){
e[++tot].to = y;
e[tot].data = z;
e[tot].nxt = head[x];
head[x] = tot;
}
inline void dfs(int x,int f,LL dis){
++cnt;
b[cnt] = v[cnt] = dis;
L[x] = cnt;
for(int i = head[x];i;i = e[i].nxt){
int y = e[i].to;
if(y == f) continue;
dfs(y,x,dis + e[i].data);
}
R[x] = cnt;
}
inline void ins(int &u,int l,int r,int x){
a[++t] = a[u];
u = t;
if(l == r){
a[u].sum++;
return ;
}
int mid = (l + r) >> 1;
if(x <= mid) ins(a[u].lc,l,mid,x);
else ins(a[u].rc,mid + 1,r,x);
a[u].sum = a[a[u].lc].sum + a[a[u].rc].sum;
}
inline int query(int u1,int u2,int l,int r,int x){
if(r < x) return a[u2].sum - a[u1].sum;
if(l >= x) return 0;
int mid = (l + r) >> 1;
if(x <= mid) return query(a[u1].lc,a[u2].lc,l,mid,x);
else return query(a[u1].rc,a[u2].rc,mid + 1,r,x) + a[a[u2].lc].sum - a[a[u1].lc].sum;
}
int main(){
n = read(),g = read();
for(int i = 2;i <= n;++i){
int x = read();LL z = read();
add(i,x,z);
add(x,i,z);
}
// cout << 1 << endl;
dfs(1,0,0);
sort(b + 1,b + n + 1);
b[0] = unique(b + 1,b + n + 1) - b - 1;
for(int i = 1;i <= cnt;++i){
rt[i] = rt[i - 1];
v[i] = lower_bound(b + 1,b + b[0] + 1,v[i]) - b;
ins(rt[i],1,b[0],v[i]);
}
b[b[0] + 1] = 1e18 + 7;
for(int i = 1;i <= n;++i){
LL k = b[v[L[i]]] + g;
k = upper_bound(b + 1,b + b[0] + 2,k) - b;
printf("%d
",query(rt[L[i] - 1],rt[R[i]],1,b[0],k));
}
return 0;
}