V. C87【树状数组+DFS】统计子树i中点权比wi大的点数[USACO17JAN] Promotion Counting P

传统题

1000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给出一棵有 $n$ 个点的有根树，根为点 $1$ ，每个节点的点权为 $w_i$ 。

求对于每个点 $i$ 为根的子树中，点权比 $w_i$ 大的节点个数。

第一行一个整数 $n$ （ $1\le n \le 10^5$ ）。

下来 $n$ 个互不相同的整数 $w_i$ （ $1 \le w_i \le 10^9$ ）。

下来 $n-1$ 行，描述了点 $2 \sim n$ 的父亲的编号。提醒，点 1 作为根，没有父亲节点。

输出 $n$ 行，每行一个整数，对于每个点 $i$ 为根的子树中，点权比 $w_i$ 大的节点个数。