rockdu
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≤i≤N ) 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<j≤N ) such that Zi>Zj.
Constraints
- 1≤N≤2×105
- 1≤Pi<i ( 2≤i≤N )
- 0≤Vi≤1 ( 1≤i≤N )
- 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.
Sample Input 1
6 1 1 2 3 3 0 1 1 0 0 0
Sample Output 1
4
When the vertices are arranged in the order 1,3,5,6,2,4, X 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.
Sample Input 2
1 0
Sample Output 2
0
X=(0), whose inversion number is 0.
Sample Input 3
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
Sample Output 3
31
题目大意：一棵树上每个节点有0，1两种数字。现在你可以按照拓扑序把树上的数字一个个放到一个序列上（也就是说父亲要比所有的儿子先拿）。问最后序列的逆序对个数最多可以是多少。
以前没有见过这种套路……感觉很神奇。
首先考虑这样一个问题：给你n个由01构成的字符串(总长不超过1e5)，问把它们按顺序串起来，逆序对最多有多少个？
这个问题其实可以用一个冒泡排序解决，我们先用默认顺序，然后考虑每一个串该不该往前挪动。如果一个串往前挪动更优的话就往前挪，更优是指移动后逆序对个数更多。假设A串在B串前，如果这时挪动B串更优的话，那么有：
A.cnt[1] * B.cnt[0] < A.cnt[0] * B.cnt[1]
我们发现这个大小关系是可传递的，不是一个偏序关系，因为它等价于
A.cnt[1] / A.cnt[0] < B.cnt[1] / B.cnt[0]
这样我们用快速排序重载运算符，总复杂度达到O(n log n)
这道题如果会了上面这个套路，应该就不难了。
我们用堆贪心：
先把每个节点都加入堆中，按0，1个数的比例大小排序。然后进行以下操作：
- 从堆中拿出一个节点，它一定是0的比例最多的
- 我们把它和它的父亲节点合并起来，变成一个新的大节点，加入堆中并更新答案
- 重复这个过程直到剩下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;
}
没有帐号? 立即注册