CF793B Alyona and a tree

题意：如果$y$在$x$的子树中且$dist(x,y)<=a_y$，则$x$控制$y$ 给定一棵树，求每个点控制了几个点 ------------ 二分+树上差分+前缀和 用一个栈保存$dfs$序 对于每个点二分它的祖先 这个祖先是满足$sum[x]+w[k]>=sum[k]$的最靠上的$x$ 然后$--ans[x-1],++ans[top-1]$做差分 $ans[k]=sigma(ans[v])$，相当于前缀和与差分的转化 ``` #include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #define reg register using namespace std; typedef long long ll; const int N=2e5+5; struct node { int to,nxt,dis; }edge[N]; int n,num,head[N],w[N],ans[N],stack[N],top; ll sum[N]; inline int read() { int x=0,w=1; char c=getchar(); while (!isdigit(c)&&c!='-') c=getchar(); if (c=='-') c=getchar(),w=-1; while (isdigit(c)) { x=(x<<1)+(x<<3)+c-'0'; c=getchar(); } return x*w; } inline void add_edge(int from,int to,int dis) { edge[++num]=(node){to,head[from],dis}; head[from]=num; } void dfs(int k) { stack[++top]=k; int l=0,r=top,pos=0; while (l<=r) { int mid=(l+r)>>1; if (sum[stack[mid]]>=sum[k]-w[k]) pos=mid,r=mid-1; else l=mid+1; } ++ans[stack[top-1]]; --ans[stack[pos-1]]; for (reg int i=head[k];i;i=edge[i].nxt) { int v=edge[i].to,d=edge[i].dis; sum[v]=sum[k]+d; dfs(v); ans[k]+=ans[v]; } --top; } int main() { n=read(); for (reg int i=1;i<=n;w[i++]=read()); for (reg int i=2;i<=n;i++) { int x=read(),y=read(); add_edge(x,i,y); } dfs(1); for (reg int i=1;i<=n;i++) printf("%d ",ans[i]); return 0; } ```