【题目大意】
给出一棵树，初始状态均为0，每反转一个节点的状态，相邻的节点（父亲或儿子）也会反转，问要使状态均为1，至少操作几次？
【思路】
一场大暴雨即将来临，白昼恍如黑夜！happy！
和POJ1222差不多，首先容易知道：每个节点最多被反转一次，证明略。
高斯消元解Xor方程组可能存在*元，即处理完后map[i][i]=0;则通过dfs来枚举所有的情况，求出最小的。
【错误点】
gauss里面交换值得时候不要忘了n+1也要跟着交换。
dfs里面的t我一开始直接是按照往常一样修改map[i][n+1],然而这个是dfs，map[i][n+1]的初始值后面还要用到。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=+;
const int INF=0x7fffffff;
int n,map[MAXN][MAXN],que[MAXN];
int ans; void Gauss()
{
for (int i=;i<=n;i++)
{
int t=i;
for (;t<=n && !map[t][i];t++);
if (t<=n)
{
if (t!=i) for (int j=i;j<=n+;j++) swap(map[i][j],map[t][j]);
for (int j=i+;j<=n;j++)
if (map[j][i])
for (int k=i;k<=n+;k++) map[j][k]^=map[i][k];//不要忘记这里要到n+1
}
}
} void dfs(int step,int now)
{
if (now>=ans) return;
if (!step)
{
ans=min(ans,now);
return;
}
if (map[step][step])
{
int t=map[step][n+];
//map[step][n+1]后续回溯中还要使用，所以要暂存给t
for (int i=step+;i<=n;i++)
if (map[step][i]) t^=que[i];//这里不要把step和i搞混了
que[step]=t;
dfs(step-,now+t);
}
else
{
que[step]=;dfs(step-,now);
que[step]=;dfs(step-,now+);
}
} void init()
{
ans=INF;
memset(que,,sizeof(que));
memset(map,,sizeof(map));
for (int i=;i<n-;i++)
{
int u,v;
scanf("%d%d",&u,&v);
map[u][v]=map[v][u]=;
}
for (int i=;i<=n;i++) map[i][i]=,map[i][n+]=;
} int main()
{
while (~scanf("%d",&n))
{
if (n==) break;
init();
Gauss();
dfs(n,);
printf("%d\n",ans);
}
return ;
}