MnZn 求调
查看原帖
MnZn 求调
415592
Anxiomgh楼主2023/9/12 23:00

题目样例输出 13。。。求大佬帮忙查错 qwq

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

#define ll long long
const int MAXN = 525050;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
	return x * f;
}

struct edge
{
	int nxt, to;
}e[MAXN << 1];
int head[MAXN], v[MAXN], cnt;
void add_edge(int u, int v)
{
	e[++cnt].nxt = head[u];
	head[u] = cnt;
	e[cnt].to = v;
}
int ch[MAXN * 30][2], root[MAXN], tot; ll w[MAXN * 30], xs[MAXN * 30];
ll ans;
void push_up(int x)
{
	w[x] = 0; xs[x] = 0;
	if (ch[x][0]) { w[x] += w[ch[x][0]]; xs[x] ^= xs[ch[x][0]] << 1; }
	if (ch[x][1]) { w[x] += w[ch[x][1]]; xs[x] ^= (xs[ch[x][1]] << 1) | (w[ch[x][1]] & 1); }
//	w[x] = w[ch[x][0]] + w[ch[x][1]];
//	xs[x] = (xs[ch[x][0]] << 1) ^ ((xs[ch[x][1]] << 1) ^ (w[ch[x][1]] & 1));
	w[x] = w[x] & 1;
}
void change(int &x, int val)
{
	if (!x) x = ++tot;
	if (!val) { w[x]++; return; }
	change(ch[x][val & 1], val >> 1);
	push_up(x);
}
void add(int x) // 全局加一 
{
	swap(ch[x][0], ch[x][1]); // 两棵子树互换
	if (ch[x][0]) add(ch[x][0]);
	push_up(x);
}
int merge(int o1, int o2)
{
	if (!o1) return o2;
	if (!o2) return o1;
	w[o1] += w[o2];
	xs[o1] ^= xs[o2];
	ch[o1][0] = merge(ch[o1][0], ch[o2][0]);
	ch[o1][1] = merge(ch[o1][1], ch[o2][1]);
	return o1;
}
void dfs(int x, int fa)
{
	for (int i = head[x]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if (v == fa) continue;
		dfs(v, x);
//		printf("%d %d\n", x, v);
		root[x] = merge(root[x], root[v]);
	}
	add(root[x]);
	change(root[x], v[x]);
//	printf("%d %lld\n", x, xs[root[x]]);
//	printf("%d\n", root[x]);
	ans += xs[root[x]];
}
int main()
{
	int n = read();
	for (int i = 1; i <= n; i++)
		v[i] = read();
	for (int i = 2; i <= n; i++)
	{
		int f = read();
		add_edge(f, i); add_edge(i, f);
	}
	dfs(1, 0);
	printf("%lld", ans);
	return 0;
}
2023/9/12 23:00
加载中...