type
status
date
slug
summary
tags
category
icon
password
题目描述
图论中的树为一个无环的无向图。给定一棵树,每个节点有一盏指示灯和一个按钮。如果节点的按扭被按了,那么该节点的灯会从熄灭变为点亮(当按之前是熄灭的),或者从点亮到熄灭(当按之前是点亮的)。并且该节点的直接邻居也发生同样的变化
开始的时候,所有的指示灯都是熄灭的。请编程计算最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态
输入格式
输入文件有多组数据
输入第一行包含一个整数 ,表示树的节点数目。每个节点的编号从 到
输入接下来的 行,每一行包含两个整数 ,,表示节点 和 之间有一条无向边
当输入 为 时,表示输入结束
输入样例
输出样例
输出格式
对于每组数据,输出最少要按多少次按钮,才能让所有节点的指示灯变为点亮状态。每一组数据独占一行。
表示以 为根的子树都亮,并且 开
表示以 为根的子辈都亮, 没开, 亮
表示以 为根的子辈都亮, 没开, 不亮
初始
如果 , ^
代表着 不会亮, 就代表着 会亮