提出 #63110177

---

ソースコード 拡げる

// LUOGU_RID: 204468291
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F(i,l,r) for(int i = (l);i <= (r);++i)
#define D(i,r,l) for(int i = (r);i >= (l);--i)
#define vt vector
#define mem(a,x) memset(a,x,sizeof a)
#define fi first
#define se second
#define pb push_back
#define bug cerr<<"LINE:"<<__LINE__<<" "
mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 1e6+10;
constexpr ll inf = 1e18,mod = 998244353;


ll read(){
	ll x = 0,f = 1;char c = getchar();
	for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
	for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
	return x * f;
}

void cmax(ll &x,ll y){x = max(x,y);}
void cmin(ll &x,ll y){x = min(x,y);}

int n;
int fa[N],w[N];

struct DSU{
	int fa[N];
	void build(){F(i,1,n)fa[i] = i;}
	int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x,int y){
		x = find(x),y = find(y);
		if(x == y)return;
		fa[x] = y;
	}
}U;

struct node{
	ll s[2];
	bool operator < (const node x)const{return s[1] * x.s[0] < x.s[1] * s[0];}
	node operator + (const node x)const{return {s[0] + x.s[0],s[1] + x.s[1]};}
};
node v[N];
set<pair<node,int> >s;
ll val(node x,node y){return x.s[1] * y.s[0];}

void solve(){
	n = read();
	ll ans = 0;
	F(i,2,n)fa[i] = read();
	F(i,1,n)w[i] = read(),v[i].s[w[i]]++;
	F(i,2,n)s.insert({v[i],i});
	U.build();
	while(s.size()){
		auto it = s.begin();
		int x = (*it).se;
		int f = U.find(fa[x]);
		s.erase({v[x],x});
		ans += val(v[f],v[x]);
		if(f != 1)s.erase({v[f],f});
		U.fa[x] = f,v[f] = v[f] + v[x];
		if(f != 1)s.insert({v[f],f});
	}
	printf("%lld\n",ans);
}

int main(){
	int t = 1;
	while(t--)solve();
	return 0;
}

提出情報

ジャッジ結果