题解 | #牛牛的树#

题意：一颗n个结点的树，每个边上都有一盏灯，给出每条边上的灯的状态，给出一些重要的边，让你每次选择一条路径翻转路径上的灯的状态，最少多少次才能使得所有重要边上的灯全部亮起来。

解：

个人觉得题目给出的图可以很好的理解答案的求解过程

（呜呜呜不知道为什么一放图片就显示不要泄漏自己的信息，然后发布完就访问不到）

只好把图片删掉啦，大家一定要注意研究题目给的图哇

图一：

选择的路径是通过根的

一个很重要的点，一个点翻转偶数次的状态和初始状态是一样的。

所以我们可以想到，每次的路径上都有根的话，可以使得每次都选择到两条需要翻转的链。 从叶子结点开始考虑，这条边是重要的并且灭着，那么我们就需要翻转这条边，否则不需要翻转。

参照样例二，需要翻转的链是0-1-4、4-5、4-6、0-2 可以发现我们1-4路径上的边只要满足翻转偶数次就可以实现继续亮着的成就。 所以每次选择两条链来翻转。

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

const int N = 100;
int n,a[N],b[N],c[N],d[N],fa[N];
char sc[N];

int main()
{
	scanf("%d",&n);
	for(int i = 2;i <= n; i++) 
		scanf("%d",&fa[i]),++fa[i];
	scanf("%s",sc + 1);
	for(int i = 2;i <= n; i++)
		a[i] = sc[i - 1] - '0';
	scanf("%s",sc + 1);
	for(int i = 2;i <= n; i++)
		d[i] = sc[i - 1] - '0';
	int ans = 0;
	for(int i = n;i >= 2; i--)
	{
		if(d[i] && (!(a[i] ^ b[i]))) c[i]=1;  //边重要并且灭着
		b[fa[i]] ^= b[i] ^ c[i];  //将翻转信息传递上去
	}
	for(int i = 2;i <= n;i++) 
		ans += c[i];//,cout<<(i - 1)<<' '<<c[i]<<endl;
	printf("%d",(ans+1) >> 1);
	return 0;
}