【题意】给定一棵树的灯，按一次x改变与x距离<=1的点的状态，求全0到全1的最少次数。n<=100。
【算法】高斯消元解异或方程组
【题解】设f[i]=0/1表示是否按第i个点的按钮，根据每个灯的亮灭可以列出n个方程：a[i][j]表示第i盏灯是否受开关j影响，a[i][n+1]=a[i][i]=1。
由于方案不唯一，所以有*元，DFS所有*元得到所有可能答案，比较得到最少次数。DFS记得加最优性剪枝。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=;
bool a[maxn][maxn],A[maxn];
int n,ans;
void gauss(){
for(int i=;i<=n;i++){
int r=i;
for(int j=i;j<=n;j++)if(a[j][i]){r=j;break;}
if(!a[r][i])continue;
if(r!=i)for(int j=i;j<=n+;j++)swap(a[i][j],a[r][j]);
for(int j=i+;j<=n;j++)if(a[j][i]){
for(int k=n+;k>=i;k--){
a[j][k]^=a[i][k];
}
}
}
}
void dfs(int x,int now){
if(now>=ans)return;
if(!x){ans=now;return;}
if(a[x][x]){
A[x]=a[x][n+];
for(int j=x+;j<=n;j++)A[x]^=a[x][j]*A[j];
dfs(x-,now+A[x]);
}
else{
A[x]=;dfs(x-,now);
A[x]=;dfs(x-,now+);
}
} int main(){
scanf("%d",&n);
while(n){
memset(a,,sizeof(a));
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
a[u][v]=a[v][u]=;
}
for(int i=;i<=n;i++)a[i][i]=a[i][n+]=;
gauss();
ans=0x3f3f3f3f;
dfs(n,);
printf("%d\n",ans);
scanf("%d",&n);
}
return ;
}