luoguP3066 [USACO12DEC]逃跑的BarnRunning

luoguP3066 [USACO12DEC]逃跑的BarnRunning

题目大意

偏模板的主席树

PS：注意一下输入格式

dfs：得出每个子树时间戳区间，每个节点到根节点的距离，仔细理解一下几个数组的含义吧，dalao直接略过

update：这题以时间戳（i）为关键字继承（i-1）

query：直接查询每个子树的时间戳区间里<=dep[i]+L

这里用到了一个小技巧，就是为了避免特判，b数组加一个虚节点inf，查询<now的就好了

My complete code：

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

const LL maxn=3e5;

const LL inf=1e18;

inline LL read(){

	LL x=0,f=1; char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') f=-1; c=getchar();

	}

	while(c>='0'&&c<='9'){

		x=x*10+c-'0'; c=getchar();

	}return x*f;

}

struct node{

	LL to,next,d;

}dis[maxn];

LL n,L,num,nod,num1,cnt;

LL head[maxn],dep[maxn],b[maxn],low[maxn],dfn[maxn],sot[maxn],date[maxn<<7],lt[maxn<<7],rt[maxn<<7],root[maxn];

inline void add(LL u,LL v,LL d){

	dis[++num]=(node){v,head[u],d}; head[u]=num;

}

void dfs(LL u,LL fa){

	sot[++num1]=u;

	b[++cnt]=dep[u];

	dfn[u]=++num;

	for(LL i=head[u];i;i=dis[i].next){

		LL v=dis[i].to;

		dep[v]=dep[u]+dis[i].d;

		dfs(v,u);

	}

	low[u]=num;

}

void update(LL &now,LL pre,LL l,LL r,LL c){

	now=++nod;

	date[now]=date[pre]+1;

	if(l==r)

	    return;

	LL mid=(l+r)>>1;

	if(c<=mid){

		update(lt[now],lt[pre],l,mid,c);

		rt[now]=rt[pre];

	}else{

		update(rt[now],rt[pre],mid+1,r,c);

		lt[now]=lt[pre];

	}

}

LL query(LL pre,LL next,LL l,LL r,LL c){//<c

	LL mid=(l+r)>>1;

	if(r<c)

	    return date[next]-date[pre];

	LL ans=0;

	if(l<c)

		ans+=query(lt[pre],lt[next],l,mid,c);

	if(mid+1<c)

		ans+=query(rt[pre],rt[next],mid+1,r,c);

	return ans;

}

int main(){

	scanf("%lld%lld",&n,&L);

	for(LL v=2;v<=n;++v){

		LL u=read(),e=read();

		add(u,v,e);

	}

	num=0;

	dfs(1,0);

	sort(b+1,b+1+cnt);

	b[++cnt]=inf;

	cnt=unique(b+1,b+1+cnt)-b-1;

	for(LL i=1;i<=n;++i){

		LL u=sot[i];

		LL now=lower_bound(b+1,b+1+cnt,dep[u])-b;

		update(root[i],root[i-1],1,cnt,now);

	}

	for(LL i=1;i<=n;++i){

		LL l=dfn[i],r=low[i];

		LL now=upper_bound(b+1,b+1+cnt,dep[i]+L)-b;

		printf("%lld\n",query(root[l-1],root[r],1,cnt,now));

	}

	return 0;

}/*

4 5

1 4

2 3

1 5

3

2

1

1

*/