Submission #2853274

---

Source Code Expand

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cctype>
#include <set>
#define R register
#define IN inline
#define W while
#define IN inline
#define gc getchar()
#define MX 200500
template <class T>
IN void in(T &x)
{
	x = 0; R char c = gc;
	W (!isdigit(c)) c = gc;
	W (isdigit(c))
	x = (x << 1) + (x << 3) + c - 48, c = gc;
}
int col[MX][2], fat[MX], bel[MX], dot;
struct Vertex
{int id;};
IN bool operator < (const Vertex &x, const Vertex &y)
{
	int x0 = col[x.id][0], x1 = col[x.id][1], y0 = col[y.id][0], y1 = col[y.id][1];
	return 1ll * x0 * y1 > 1ll * x1 * y0 || 
	(1ll * x0 * y1 == 1ll * x1 * y0 && x.id > y.id);
}
std::set <Vertex> st;
long long ans;
namespace DSU
{
	int find(R int now) {return bel[now] == now ? now : bel[now] = find(bel[now]);}
	IN void combine(const int &from, const int &to) {bel[from] = find(to); col[to][0] += col[from][0], col[to][1] += col[from][1];}
}
int main(void)
{
	in(dot); R int a, now, fa;
	for (R int i = 2; i <= dot; ++i) in(fat[i]);
	for (R int i = 1; i <= dot; ++i) in(a), ++col[i][a], bel[i] = i;
	for (R int i = 2; i <= dot; ++i) st.insert({i});
	W (!st.empty())
	{
		now = DSU::find(st.begin() -> id);
		st.erase(st.begin());
		fa = DSU::find(fat[now]); st.erase({fa});
		ans += 1ll * col[fa][1] * col[now][0];
		DSU::combine(now, fa);
		if(fa != 1) st.insert({fa});
	}
	printf("%lld", ans);
}

Submission Info

Judge Result