Chika and Reverse Pairs on Tree【17th UESTC电子科技大学校赛 I题】

  题目问的就是对于每个节点，它的子节点中有多少对是我们所要找的节点对，我们要找的节点对得满足这样的条件，a[祖先] > a[u]，不一定是父节点的说，可以是祖父级别。

  我们可以这样推，从叶子节点往上，我们找到每个节点的权值，先去用dp[]记录以该节点为根的符合条件的节点的个数，然后我们再向下，找到它下面的所有节点的比他小的节点个数（严格小于），用到线段树合并的思维。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, a[maxN], lsan[maxN], diff, head[maxN], cnt, root[maxN], tree[maxN * 40], lc[maxN * 40], rc[maxN * 40], tot;
ll dp[maxN];    //这个会被卡掉，要开long long
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
}edge[maxN];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
inline void pushup(int rt) { tree[rt] = tree[lc[rt]] + tree[rc[rt]]; }
inline void Merge(int p1, int p2, int l, int r)
{
    if(l == r)
    {
        tree[p1] += tree[p2];
        return;
    }
    int mid = HalF;
    if(lc[p1] && lc[p2]) Merge(lc[p1], lc[p2], l, mid);
    else if(lc[p2]) lc[p1] = lc[p2];
    if(rc[p1] && rc[p2]) Merge(rc[p1], rc[p2], mid + 1, r);
    else if(rc[p2]) rc[p1] = rc[p2];
    pushup(p1);
}
inline void insert(int &rt, int l, int r, int pos)
{
    if(!rt) rt = ++tot;
    tree[rt]++;
    if(l == r) return;
    int mid = HalF;
    if(pos <= mid) insert(lc[rt], l, mid, pos);
    else insert(rc[rt], mid + 1, r, pos);
}
int query(int rt, int l, int r, int ql, int qr)
{
    if(ql <= l && qr >= r) return tree[rt];
    int mid = HalF;
    if(qr <= mid) return query(lc[rt], l, mid, ql, qr);
    else if(ql > mid) return query(rc[rt], mid + 1, r, ql, qr);
    else return query(lc[rt], l, mid, ql, qr) + query(rc[rt], mid + 1, r, ql, qr);
}
void dfs(int u)
{
    dp[u] = 0;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        dfs(v);
        dp[u] += dp[v];
        Merge(root[u], root[v], 1, diff);
    }
    int tall = (int)(lower_bound(lsan + 1, lsan + diff + 1, a[u]) - lsan);
    insert(root[u], 1, diff, tall);
    if(tall > 1) dp[u] += query(root[u], 1, diff, 1, tall - 1);
}
inline void init()
{
    cnt = 0;    tot = N;
    memset(head, -1, sizeof(head));
    memset(lc, 0, sizeof(lc));
    memset(rc, 0, sizeof(rc));
    memset(tree, 0, sizeof(tree));
}
int main()
{
    scanf("%d", &N);
    init();
    for(int i=1; i<=N; i++) { scanf("%d", &a[i]); lsan[i] = a[i]; root[i] = i; }
    for(int i=2, fa; i<=N; i++)
    {
        scanf("%d", &fa);
        addEddge(fa, i);
    }
    sort(lsan + 1, lsan + N + 1);
    diff = (int)( unique(lsan + 1, lsan + N + 1) - lsan - 1 );
    dfs(1);
    for(int i=1; i<=N; i++) printf("%lld\n", dp[i]);
    return 0;
}