AT_arc169_a的题解

关于我在赛场上一题都没有切，后面自己推出来正解这件事~

题面翻译

给定一个长度为 \(N\) 的整数序列 \(A=( A_1, A_2,\cdots,A_N)\) 和另一个长度为 \(N-1\) 的整数序列 \(P=(P_2,\cdots,P_N)\)。注意 \(P\) 的索引从 \(2\) 开始。对于每个 \(i\)，保证 \(1 \leq P_i < i\)。

现在您将重复下面的操作 \(10^{100}\) 次。

• 为每一个 \(i=2,\cdots,N\) 的值，\(A_{P_i}=A_{P_i}+A_i\)

确定当所有操作完成时，\(A_1\) 是正的、负的还是零。

题目想让你求什么

给你一棵以 \(1\) 为根的树，\(i\) 号点的父亲是 \(P_i\)，点权是 \(A_i\)，重复 \(10^{100}\) 次，从 \(1\sim N\) 分别将 \(i\) 号点的点权加进其父亲的点权。请判断 \(1\) 号点点权的正负性。

题目思路

我们发现，深度最深的点起决定性作用，因为无限次之后如果深度最深的点是负的，那么肯定能把深度较浅的点减成负的。如果深度最深的点是正的，那么肯定能把深度较浅的点加成正的。

所以，我们可以想到使用拓扑进行图的分层，求出每一层的和，在从下向上比较，当最底下一层的和为 \(0\) 时，该层对答案无影响，再看上面一层（可以把 \(1\) 号节点设为根）。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void read(ll &s)
{
	s = 0;
	char ch = getchar(), lst = ' ' ;
	while (ch < '0' || ch > '9')
		lst = ch, ch = getchar();
	while (ch >= '0' && ch <= '9')
		s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
	if (lst == '-')
		s = -s;
}

ll n;
ll a[250005];
struct node
{
	ll to, nxt;
};
node edge[250005];
ll hd[250005], cnt;
ll flr, sum[250005];
ll h, r, q[250005];
void add(ll x, ll y)
{
	cnt++;
	edge[cnt].to = y;
	edge[cnt].nxt = hd[x];
	hd[x] = cnt;
}

int main()
{
	read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	for (int i = 2; i <= n; i++)
	{
		read(a[0]);
		add(a[0], i);
	}
	q[r++] = 1;
	sum[++flr] = a[1];
	while (h < r)
	{
		flr++;
		ll t = r;
		while (h < t)
		{
			for (int i = hd[q[h]]; i; i = edge[i].nxt)
				q[r++] = edge[i].to;
			sum[flr] += a[q[h]];
			h++;
		}
	}
	int flag = 0;
	for (int i = flr; i; i--)
		if (sum[i] > 0)
		{
			flag = 1;
			break;
		}
		else if (sum[i] < 0)
		{
			flag = -1;
			break;
		}
	if (flag > 0)
		printf("+");
	else if (flag == 0)
		printf("0");
	else
		printf("-");
	return 0;
}

尾声

感谢以为大佬告诉我这题可以用拓扑的思想，同时感谢martian148大佬为本篇题解提供写法上的参考。