CodeForces - 739B Alyona and a tree(树上差分+二分)

思路

很显然对于任意一个点u，如果有一个点v满足dist(v,u)<=a[u],那么v到u路径上的所有点都是满足条件的点。所以我们考虑二分（也可以倍增），找到第一个符合条件的点。然后我们使用树上差分来统计结果。我们令所有点ans=1，再对符合条件的点的父亲我们ans—，最后dfs的时候从子节点往父节点合并答案即可。注意最后答案要ans-1，因为初始ans=1即自己被多统计了一次。

代码

#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

const int MAXN=200005;
int ans[MAXN];
ll dis[MAXN],a[MAXN];
vector<pair<int,ll> > G[MAXN];
vector<pair<ll,int> > que;

void dfs(int x){
	ans[x]=1;
	ll t=dis[x]-a[x];
	int pos=lower_bound(que.begin(),que.end(),make_pair(t,0))-que.begin();
	pos--;
	if(pos>=0)ans[que[pos].second]--;
	que.push_back(make_pair(dis[x],x));
	for(vector<pair<int,ll> >::iterator it=G[x].begin();it!=G[x].end();it++){
		dis[it->first]=dis[x]+it->second;
		dfs(it->first);
		ans[x]+=ans[it->first];
	}
	que.pop_back();
}

int main() {
	int n,v;
	ll w;
	while(~scanf("%d",&n)){
		ms(ans,0),ms(dis,0);
		for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
		for(int i=1;i<n;i++){
			scanf("%d%lld",&v,&w);
			G[v].push_back(make_pair(i+1,w));
		}
		dfs(1);
		for(int i=1;i<=n;i++){
			if(i>1)printf(" ");
			printf("%d",ans[i]-1);
		}
		printf("\n");
		que.clear();
		for(int i=0;i<MAXN;i++)G[i].clear();
	}
	return 0;
}