[文章目录]
Description
图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。开始的时候，所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。n<=100
话说高斯消元不是很懂啊。。。什么“搞死小圆一下+爆枚自由元”什么的，感觉我好菜啊。。
好像树形DP更优一些啊。。。设f[x][a][b]表示x按，不按，亮，不亮的方案数。推一推就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=200;//inf不能设太大，会加爆
int n;
int head[110],to[210],nxt[210],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt;
}
int f[110][2][2];
void dfs(int x,int pre)
{
f[x][1][0]=f[x][0][1]=inf; f[x][0][0]=0; f[x][1][1]=1;
int a,b,c,d,y;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
{
y=to[i]; dfs(y,x);
a=f[x][0][0],b=f[x][0][1],c=f[x][1][0],d=f[x][1][1];
f[x][0][0]=min(b+f[y][1][1],a+f[y][0][1]);
f[x][0][1]=min(a+f[y][1][1],b+f[y][0][1]);
f[x][1][0]=min(d+f[y][1][0],c+f[y][0][0]);
f[x][1][1]=min(c+f[y][1][0],d+f[y][0][0]);
}
}
int main()
{
while(1)
{
memset(head,0,sizeof head); cnt=0;
scanf("%d",&n); int x,y;
if(!n) return 0;
for(int i=1;i!=n;++i)
{
scanf("%d%d",&x,&y);
add(x,y);
}
dfs(1,0);
printf("%d\n",min(f[1][1][1],f[1][0][1]));
}
}