[USACO17JAN] Promotion Counting晋升者计数 (树状数组+dfs)

#include #define dd double
#define N 100100
using namespace std;

int n,cnt,ma,lst;
int a[N],head[N],s[N],ans[N];
struct EDGE{
    int to,nxt;
}edge[N*2];
struct node{
    int og,mx,id;
}d[N];
int cmp1(node a,node b) {return a.ogb.og;}
int cmp2(node a,node b) {return a.idb.id;}
void update(int x,int p)
{
    for(int i=x;ii)))
    {
        s[i] += p; 
    }
}
int query(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=(i&(-i)))
    {
        ans += s[i];
    }
    return ans;
}
void edge_add(int u,int v)
{
    cnt++;
    edge[cnt].to = v;
    edge[cnt].nxt= head[u];
    head[u] = cnt;
}
void discrete()
{
    sort(d+1,d+n+1,cmp1);
    for(int i=1;i)
    {
        if(d[i].og==d[i-1].og)
        {
            d[i].mx=d[i-1].mx;
        }else{
            d[i].mx=++ma;
        }
    }
    sort(d+1,d+n+1,cmp2);
    for(int i=1;i d[i].mx;
}
void dfs(int x,int fa)
{
    for(int j=head[x];j!=-1;j=edge[j].nxt)
    {
        int v=edge[j].to;
        if(v==fa) continue;
        int s1=query(ma)-query(a[x]);
        dfs(v,x);
        int s2=query(ma)-query(a[x]);
        ans[x] += s2-s1;
    }
    update(a[x],1);
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i"%d",&d[i].og);d[i].id=i;}
    memset(head,-1,sizeof(head));
    int x;
    for(int i=2;i)
    {
        scanf("%d",&x);
        edge_add(i,x);
        edge_add(x,i);
    }
    discrete();
    dfs(1,-1);
    for(int i=1;i"%d\n",ans[i]);
    return 0;
}