标签：tmp cnt int TurnOnLamps st fa fl

贪心

贪心的从下往上，对于当前位，如果这一位是任意的，那么如果它有儿子可以向上，那么当前点选择为翻转是肯定不劣的，而如果没有儿子向上，那么当前点选中一定是不优的

然后数向上的儿子个数，每 \(2\) 个可以合并为 \(1\) 条路径

如果一个点合并后不满足限制，则通过从当前点重新出发一条链来使它合法

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

int n;
int fa[N];
vector<int> g[N];
bool st[N], qry[N];
bool fl[N];
int res = 0;

void dfs(int x, int fa)
{
	int cnt = 0;
	fl[x] = false;
	for (auto v : g[x])
	{
		if (v == fa)
			continue;
		dfs(v, x);
		cnt += fl[v];
	}
	res -= cnt / 2;
	fl[x] = (cnt & 1);
	if (((!(cnt & 1)) && qry[x] && !st[x]) || ((cnt & 1) && qry[x] && st[x]))
	{
		if (!st[x])
		{
			fl[x] = true;
			res++;
		}
		else
			fl[x] = false;
	}
	// debug(x, res);
}

void solve()
{
	cin >> n;
	rep(i, 1, n)
	{
		cin >> fa[i];
		g[fa[i]].push_back(i);
	}
	string tmp;
	cin >> tmp;
	rep(i, 1, n) st[i] = tmp[i - 1] - '0';
	cin >> tmp;
	rep(i, 1, n) qry[i] = tmp[i - 1] - '0';
	dfs(0, 0);
	cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签：tmp,cnt,int,TurnOnLamps,st,fa,fl
From： https://www.cnblogs.com/xiaruize/p/18119842