50分求助
查看原帖
50分求助
701221
Chr0n1CleC楼主2023/12/23 16:06

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

const int N = 1500009;

int ch[N][2], fa[N], a[N], no[N][9], tg[N];

vector < int > G[N];

void upt(int p)
{
	if (p)
		a[p] ^= 3, swap(no[p][1], no[p][2]), tg[p] ^= 1;
}

void pd(int p)
{
	if (tg[p])
		upt(ch[p][0]), upt(ch[p][1]), tg[p] = 0;
}

void up(int p)
{
	pd(p);
	for (int i = 1;i <= 2;++ i)
		if (no[ch[p][1]][i])
			no[p][i] = no[ch[p][1]][i];
		else if (a[p] != i)
			no[p][i] = p;
		else
			no[p][i] = no[ch[p][0]][i];
}

int get(int x)
{
	return x == ch[fa[x]][1];
}

int nrt(int x)
{
	return x == ch[fa[x]][1] || x == ch[fa[x]][0];
}

void ror(int x)
{
	int y = fa[x], z = fa[y], f = get(x);
	pd(z), pd(y), pd(x);
	if (nrt(y))
		ch[z][get(y)] = x;
	ch[y][f] = ch[x][!f], fa[ch[x][!f]] = y;
	ch[x][!f] = y, fa[y] = x, fa[x] = z;
	up(y), up(x), up(z);
}

void Up(int p)
{
	if (nrt(p))
		Up(fa[p]);
	pd(p);
}

void spl(int p)
{
	Up(p);
	while (nrt(p))
		ror(p); 
}

void access(int x)
{
	for (int p = 0;x;x = fa[p = x])
		spl(x), ch[x][1] = p, up(x);
}

void cg(int x)
{
	access(x), spl(x);
	int v = a[x];
	int cr = no[ch[x][0]][(v == 3) + 1];
	if (cr)
		spl(cr), upt(ch[cr][1]), a[cr] += (v == 3) ? -1 : 1, up(cr);
	else
		upt(x);
	spl(x);
}

void dfs(int u)
{
	for (int v : G[u])
		dfs(v), a[u] += (a[v] > 2);
	up(u); 
}

int main()
{
	int n, m;
	scanf("%d", &n);
	for (int i = 1, x;i <= n;++ i)
		for (int j = 0;j < 3;++ j)
			scanf("%d", &x), G[i].push_back(x), fa[x] = i;
	for (int i = n + 1;i <= 3 * n + 1;++ i)
		scanf("%d", &a[i]), a[i] *= 3;
	dfs(1);
	scanf("%d", &m);
	for (int x;m --;)
		scanf("%d", &x), cg(x), spl(1), printf("%d\n", (a[1] > 1));
	
	return 0;
}
2023/12/23 16:06
加载中...