树上关灯

[ruijianjixie1]

树上关灯 题目描述 小红得到一棵节点数为 � n 的树，树上每个节点都有一盏初始状态为“开启”的灯。小红每次操作可改变相邻两盏灯的状态（开变关，关变开） ，她希望通过操作使树上不存在两盏相邻的灯同时处于开启状态，求至少需要操作的次数。树上两个节点相邻当且仅当它们之间有边相连。

输入格式 第一行输入一个正整数 � n（ 1 ≤ � ≤ 10 5 1≤n≤10 5 ），表示树的节点数量。 接下来 � − 1 n−1 行，每行输入两个正整数 � , � u,v（ 1 ≤ � , � ≤ � 1≤u,v≤n ），表示节点 � u 和节点 � v 相邻。 输出格式 输出一个正整数 � k ，代表使树上不存在相邻开启灯时操作的最小次数。

输入输出样例 输入样例 1 6 1 2 1 3 1 4 4 5 4 6 输出样例 1 1 样例 1 说明 只需要操作1次，对1和4号节点操作，它们的灯均被关闭，此时不存在两个相邻的灯同时开启。