解题思路
固定一棵无向树。以交换机 r 为总控时，记节点 u 的辖区规模为 szr(u)。需要对每个 r 统计满足 szr(u) 为偶数的节点个数。
采用两次 DFS 的换根 DP。
- 第一次 DFS 以 1 为总控，求出每个节点的子树规模 sz[u]，并得到答案 ans[1]。
- 第二次 DFS 把总控从父节点 u 移到子节点 v。除 u 与 v 外，其余节点的辖区结构不变。移动前后：
题目内容
机房有 n 台交换机，用 n−1 条网线连成一棵树（连通无环）。以某台交换机 r 为总控时，每台交换机 u 管辖一棵子树：包含 u 及其全部后代，该子树的规模定义为其中交换机的台数。
对每个可能的总控 r=1,2,…,n，统计有多少台交换机的辖区规模为偶数。
交换机台数不超过 105。
输入描述
第一行包含一个整数 n，表示交换机台数，满足 1≤n≤105。
接下来 n−1 行，每行两个整数 ui 和 vi，表示一台交换机 ui 与 vi 之间有一条网线，满足 1≤ui,vi≤n 且 $u_i
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
