BZOJ-4756: [Usaco2017 Jan]Promotion Counting

[文章目录]

Description

n只奶牛构成了一个树形的公司,每个奶牛有一个能力值pi,1号奶牛为树根。问对于每个奶牛来说,它的子树中有几个能力值比它大的。n<=100000

记录每个节点dfs入栈序,然后将节点按照p排序,从大到小加点。将比节点权值大的先加入,然后查询子树区间和。树状数组维护。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
struct node
{
    int w,id;
}a[101000];
int head[101000],nxt[101000],to[101000],cnt;
void add(int x,int y)
{
    to[++cnt]=y;
    nxt[cnt]=head[x];
    head[x]=cnt;
}
int in[101000],out[101000],tot;
void dfs(int x)
{
    in[x]=++tot;
    for(int i=head[x];i;i=nxt[i])
        dfs(to[i]);
    out[x]=tot;
}
bool cmp(node x,node y){return x.w>y.w;}
int ans[101000],f[101000];
void fix(int x) {while(x>0) f[x]++,x-=-x&x;}
int query(int x)
{
    int re=0;
    while(x<=tot) re+=f[x],x+=-x&x;
    return re;
}
int main()
{
    scanf("%d",&n);
    int i,x;
    for(i=1;i<=n;++i) scanf("%d",&a[i].w),a[i].id=i;
    for(i=2;i<=n;++i)
    {
        scanf("%d",&x);
        add(x,i);
    }
    dfs(1);
    sort(a+1,a+n+1,cmp);
    for(i=1;i<=n;++i)
    {
        ans[a[i].id]=query(in[a[i].id])-query(out[a[i].id]+1);
        fix(in[a[i].id]);
    }
    for(i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注