CF793B Alyona and a tree

2018-09-21 21:43:23


题意:如果 $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;
}