题目链接:F - 01 on Tree
题目大意:给定一棵 (n(nleq 2 imes 10^5)) 个点的树,每一个节点上的取值是 ({0,1}),每一次选择一个没有被删除的点删除,并且加入答案序列的末尾,求出最后答案序列的最小的逆序对数。
题解:如果让逆序对数最少,那么有一个很明显的贪心就是 0
尽量放到序列的前面,所以说我们可以考虑每一个点的贡献和它的父亲合并,用一个堆维护贪心即可,然后在拿一个并查集搞一下联通块就做完了。
时间复杂度 (O(nlog n))。
代码:
#include <queue>
#include <cstdio>
using namespace std;
typedef long long ll;
const int Maxn=200000;
int n;
int fa[Maxn+5];
int head[Maxn+5],arrive[Maxn+5],nxt[Maxn+5],tot;
void add_edge(int from,int to){
arrive[++tot]=to;
nxt[tot]=head[from];
head[from]=tot;
}
int a[Maxn+5];
int f[Maxn+5];
struct Value{
int id;
int cnt_0,cnt_1;
Value(int _cnt_0=0,int _cnt_1=0,int _id=0){
cnt_0=_cnt_0;
cnt_1=_cnt_1;
id=_id;
}
friend Value operator +(Value a,Value b){
Value ans;
ans.cnt_0=a.cnt_0+b.cnt_0;
ans.cnt_1=a.cnt_1+b.cnt_1;
ans.id=a.id;
return ans;
}
Value operator +=(Value b){
(*this)=(*this)+b;
return (*this);
}
friend bool operator <(Value a,Value b){
return 1ll*a.cnt_0*b.cnt_1<1ll*a.cnt_1*b.cnt_0;
}
friend bool operator >(Value a,Value b){
return 1ll*a.cnt_0*b.cnt_1>1ll*a.cnt_1*b.cnt_0;
}
friend bool operator ==(Value a,Value b){
return a.cnt_0==b.cnt_0&&a.cnt_1==b.cnt_1&&a.id==b.id;
}
friend bool operator !=(Value a,Value b){
return !(a==b);
}
}val[Maxn+5];
priority_queue<Value> q;
int find(int x){
if(x==f[x]){
return x;
}
return f[x]=find(f[x]);
}
void merge(int x,int y){
int fa_x=find(x),fa_y=find(y);
if(fa_x==fa_y){
return;
}
val[fa_x]+=val[fa_y];
f[fa_y]=fa_x;
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++){
scanf("%d",&fa[i]);
add_edge(fa[i],i);
}
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
f[i]=i;
}
for(int i=1;i<=n;i++){
if(a[i]==0){
val[i]=Value(1,0,i);
}
else{
val[i]=Value(0,1,i);
}
}
for(int i=2;i<=n;i++){
q.push(val[i]);
}
ll ans=0;
while(!q.empty()){
Value u=q.top();
q.pop();
if(val[find(u.id)]!=u){
continue;
}
int x=u.id,y=find(fa[x]);
ans+=1ll*val[y].cnt_1*val[x].cnt_0;
merge(y,x);
if(y>1){
q.push(val[y]);
}
}
printf("%lld
",ans);
return 0;
}