题目描述

Description

图论中的树为一个无环的无向图。给定一棵树，每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了，那么该节点的灯会从熄灭变为点亮（当按之前是熄灭的），或者从点亮到熄灭（当按之前是点亮的）。并且该节点的直接邻居也发生同样的变化。
开始的时候，所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。

Input

输入文件有多组数据。
输入第一行包含一个整数n，表示树的节点数目。每个节点的编号从1到n。
输入接下来的n – 1行，每一行包含两个整数x，y，表示节点x和y之间有一条无向边。
当输入n为0时，表示输入结束。

Output

对于每组数据，输出最少要按多少次按钮，才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。

Sample Input

3
1 2
1 3
0

Sample Output

1

HINT

对于100%的数据，满足1 <= n <=100。

题目分析

树形DP
表示x自身按钮按/没按，x自身是亮/不亮的 最小次数
注意极大值不要太大

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,tot;
int head[10010],to[20010],net[20010];
int f[101][3][3];
void add(int x,int y)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y;
}
void dfs(int x,int temp)
{
    f[x][0][0]=0,f[x][1][1]=1;
    f[x][0][1]=f[x][1][0]=1000;
    for(int tmp,i=head[x];i;i=net[i])
    {
        if(to[i]==temp) continue;
        dfs(to[i],x);
        tmp=f[x][0][0]; 
        f[x][0][0]=min(f[x][0][1]+f[to[i]][1][1],f[x][0][0]+f[to[i]][0][1]);
        f[x][0][1]=min(f[x][0][1]+f[to[i]][0][1],tmp+f[to[i]][1][1]);
        tmp=f[x][1][0];
        f[x][1][0]=min(f[x][1][1]+f[to[i]][1][0],f[x][1][0]+f[to[i]][0][0]);
        f[x][1][1]=min(f[x][1][1]+f[to[i]][0][0],tmp+f[to[i]][1][0]);
    }
}
void work()
{   
    //scanf("%d",&n);
    memset(head,0,sizeof head),tot=0;
    for(int x,y,i=1;i<n;i++)
        scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1,0);
    printf("%d\n",min(f[1][1][1],f[1][0][1]));
    return ;
}
int main()
{
    while(scanf("%d",&n)!=EOF&&n) work();
}