【luogu AT3957】[AGC023F] 01 on Tree
01 on Tree
题目链接:luogu AT3957
题目大意
有一棵根为 \(1\) 的树,每个节点有个值 \(0\) 或 \(1\)。
然后每次你可以把一个没有父亲的点删除,然后把值放进一个数组里。
要你得出的数组逆序对尽可能少,要输出这个最小的逆序对个数。
思路
那我们会发现从根节点开始删会很麻烦,很难处理,那我们考虑反着来:从叶节点开始不断合并,向根节点上传答案。
那我们要先发现一件事,对于一个点 \(x\) 的一个子树 \(y\),它不管 \(y\) 里面怎么排列,里面产生了多少个逆序对,最终排列 \(x\) 里面的每个子树的时候,看的只是 \(y\) 里面有多少个 \(0\),多少个 \(1\),是不会管里面怎么排列的。
那我们就可以对于每个子树都看它怎么排列好。我们贪心一下。
首先,对于两个子树 \(i,j\),设它们 \(0\) 的数量为 \(num0_i,num0_j\),\(1\) 的数量为 \(num1_i,num1_j\)。
那如果 \(i\) 在 \(j\) 的前面,新增逆序对的个数就是 \(num1_i\times num0_j\)。如果在后面,就是 \(num1_j\times num0_i\)。
那假设 \(i\) 放前面比 \(j\) 放前面优,那就是 \(num1_i\times num0_j < num1_j\times num0_i\)。
那这个我们可以用堆来维护。
但是这是不能直接递归来搞的,我们要把每个点都看成独立,然后想父亲的方向合并。
那其实 \(num0,num1\) 记录的其实变成了这个点所在的连通块的 \(0,1\) 个数。
那显然上面的贪心在这里还是可以的。
那我们要维护 \(0,1\) 个数,自然要用并查集。
记得要判断当前点是否被删掉,因为当合并完之后,它父亲节点要删去,我们只要看 \(num0,num1\),就可以得知是否被合并。
还有一点就是 \(1\),也就是根节点是不用再合并的,因为没有父亲。
代码
#include<queue>
#include<cstdio>
using namespace std;
struct Teap {
int x, num_1, num_0;
};
bool operator < (Teap x, Teap y) {//用堆将点按贪心思想排序
return 1ll * x.num_0 * y.num_1 < 1ll * x.num_1 * y.num_0;
}
int n, a[200001], father[200001];
int fa[200001], num[200001][2];
long long ans;
priority_queue <Teap> q;
int find(int now) {//并查集
if (father[now] == now) return now;
return father[now] = find(father[now]);
}
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%d", &fa[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
num[i][a[i]]++;
father[i] = i;
}
for (int i = 2; i <= n; i++)
q.push((Teap){i, num[i][1], num[i][0]});
while (!q.empty()) {
Teap now = q.top();
q.pop();
int x = find(now.x);
if (num[x][0] != now.num_0 || num[x][1] != now.num_1)
continue;//这个点已近被删除
int y = find(fa[x]);
ans += 1ll * num[x][0] * num[y][1];//加上逆序对个数
num[y][0] += num[x][0];//这个子树所包含的0/1的个数增加
num[y][1] += num[x][1];
father[x] = y;//并查集连接
if (y != 1)//继续下去
q.push((Teap){y, num[y][1], num[y][0]});
}
printf("%lld", ans);
return 0;
}
最新文章
- lua table序列化和反序列化
- sina sae开发中出现的问题
- JavaScript一些基础技巧和注意事项,你了解这些吗?
- DEV中dx:ASPxPopupControl 控件的使用(在窗口关闭或隐藏时,清楚文本框中的内容)
- nginx 重写 rewrite 基础及实例
- Linux--U盘安装Ubuntu12.04
- Object-C 入门
- 屏幕输出VS文件输出
- 用javascript 面向对象制作坦克大战(三)
- 腾讯QQ表情为什么如此成功呢
- LeetCode_Interleaving String
- C# 仿金山毒霸启动和关闭淡入淡出效果
- 6、50道JAVA基础编程练习题跟答案
- 最小截断[AHOI2009]
- UWP 手绘视频创作工具技术分享系列 - 手绘视频与视频的结合
- Linux的安装以及部署一
- go语言入门(Hello World)
- 转://Oracle 11gR2 ASM磁盘组管理
- Advanced Installer 14.9 – WPF或winform应用程序打包成exe文件
- Knockout.Js官网学习(selectedOptions绑定、uniqueName 绑定)