[USACO17JAN] 晋升者计数 dfs序+树状数组

题面 洛谷P3605

题意：一棵有点权的树，找出树中所有\((u,v)\)的对数，其中\(u,v\)满足\(val(u)\le val(v)\)并且\(u\)为\(v\)的祖先。

本来想用dfs序+主席树做，每次查询\(u\)在其子树的大小排名，但是因为不熟写挂了，以后填坑

瞄了一眼题解，发现树状数组就可以水过，仿照查询逆序对的思路，离散化后，每次在dfs子树前存一个\(sum1\)，表示比当前节点大的个数，遍历完子树后再算出\(sum2\)，当前答案显然为\(sum2-sum1\)

#include <cstdio>

#include <algorithm>

#define MAXN 100010

#define lowbit(x) ((x)&(-(x)))

using namespace std;

int n;

int tre[MAXN];

int head[MAXN],nxt[MAXN*2],vv[MAXN],tot;

inline void add_edge(int u, int v){

    vv[++tot]=v;

    nxt[tot]=head[u];

    head[u]=tot;

}

void add(int x, int val){

    for(int i=x;i<=n;i+=lowbit(i))

        tre[i]+=val;

}

int get_sum(int x){

    int ans=0;

    for(int i=x;i>0;i-=lowbit(i))

        ans+=tre[i];

    return ans;

}

struct nod{

    int val, ord;

} cow[MAXN];

int ran[MAXN];

bool cmp(const nod &a, const nod &b){

    return a.val>b.val;

}

int ans[MAXN];

void dfs(int u){

    add(ran[u], 1);

    int sum=get_sum(ran[u]);

    for(int i=head[u];i;i=nxt[i]){

        int v=vv[i];

        dfs(v);

    }

    ans[u]=get_sum(ran[u])-sum;

}

int main() {

    scanf("%d", &n);

    for(int i=1;i<=n;++i) scanf("%d", &cow[i].val),cow[i].ord=i;

    sort(cow+1, cow+1+n, cmp);

    for(int i=1;i<=n;++i) ran[cow[i].ord]=i;

    for(int i=2;i<=n;++i){

        int t;scanf("%d", &t);

        add_edge(t, i);

    }

    dfs(1);

    for(int i=1;i<=n;++i) printf("%d\n", ans[i]);

    return 0;

}