【题意】给定一棵树的灯，按一次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
      
       #include
       
        #include
        
         using namespace std;const int maxn=110;bool a[maxn][maxn],A[maxn];int n,ans;void gauss(){    for(int i=1;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+1;j++)swap(a[i][j],a[r][j]);        for(int j=i+1;j<=n;j++)if(a[j][i]){            for(int k=n+1;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+1];        for(int j=x+1;j<=n;j++)A[x]^=a[x][j]*A[j];        dfs(x-1,now+A[x]);    }    else{        A[x]=0;dfs(x-1,now);        A[x]=1;dfs(x-1,now+1);    }}    int main(){    scanf("%d",&n);    while(n){        memset(a,0,sizeof(a));        for(int i=1;i