AGC023 F - 01 on Tree
? 解题记录 ? ? Atcoder ? ? 堆 ? ? 贪心 ? ? 并查集 ?    2018-07-15 10:47:36    1111    0    0

### Problem Statement

Snuke has a rooted tree with N vertices, numbered 1 through N. Vertex 1 is the root of the tree, and the parent of Vertex i ( 2≤iN ) is Vertex Pi ( Pi<i ). There is a number, 0 or 1, written on each vertex. The number written on Vertex i is Vi.

Snuke would like to arrange the vertices of this tree in a horizontal row. Here, for every vertex, there should be no ancestor of that vertex to the right of that vertex.

After arranging the vertices, let X be the sequence obtained by reading the numbers written on the vertices from left to right in the arrangement. Snuke would like to minimize the inversion number of X. Find the minimum possible inversion number of X.

### Notes

The inversion number of a sequence Z whose length N is the number of pairs of integers i and j ( 1≤i<jN ) such that Zi>Zj.

### Constraints

• 1≤N≤2×105
• 1≤Pi<i ( 2≤iN )
• 0≤Vi≤1 ( 1≤iN )
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

```N
P2 P3 … PN
V1 V2 … VN```

### Output

Print the minimum possible inversion number of X.

Copy
```6
1 1 2 3 3
0 1 1 0 0 0```

### Sample Output 1

Copy
`4`

When the vertices are arranged in the order 1,3,5,6,2,4X will be (0,1,0,0,1,0), whose inversion number is 4. It is impossible to have fewer inversions, so the answer is 4.

Copy
```1

0```

### Sample Output 2

Copy
`0`

X=(0), whose inversion number is 0.

### Sample Input 3

Copy
```15
1 2 3 2 5 6 2 2 9 10 1 12 13 12
1 1 1 0 1 1 0 0 1 0 0 1 1 0 0```

Copy
`31`

## 先把每个节点都加入堆中，按0，1个数的比例大小排序。然后进行以下操作：

1. 从堆中拿出一个节点，它一定是0的比例最多的
2. 我们把它和它的父亲节点合并起来，变成一个新的大节点，加入堆中并更新答案
3. 重复这个过程直到剩下1个节点

## 合并这步我们可以用并查集做，最后就能得到答案了。

```#include<cstdio>
#include<queue>
#include<algorithm>
#define	LL long long
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 2e5 + 5;
struct _01 {
int c0, c1, id;
bool operator < (const _01 & A) const {
return 1ll * c0 * A.c1 < 1ll * A.c0 * c1;
}
};
priority_queue<_01 > q;
int fa[maxn], n, a, u, v, cnt[maxn][2];
LL ans;

namespace DSU {
int fa[maxn];
void init(int n) {For(i, 0, n) fa[i] = i;}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void combine(int a, int b) {fa[find(a)] = find(b);}
}

int main() {
scanf("%d", &n), DSU::init(n);
For(i, 2, n) scanf("%d", &fa[i]);
For(i, 1, n) {
scanf("%d", &a), u = a == 0, v = a == 1, cnt[i][a] = 1;
}
For(i, 2, n) q.push((_01){cnt[i][0], cnt[i][1], i});
_01 now;
while(!q.empty()) {
now = q.top(), q.pop();
u = DSU::find(now.id);
if(cnt[u][0] == now.c0 && cnt[u][1] == now.c1) {
v = DSU::find(fa[u]);
ans += 1ll * cnt[v][1] * cnt[u][0];
cnt[v][1] += cnt[u][1];
cnt[v][0] += cnt[u][0];
DSU::combine(u, v);
if(v != 1) q.push((_01) {cnt[v][0], cnt[v][1], v});
}
}
printf("%lld", ans);
return 0;
}```

1111 人读过

0 条评论