由于周末有数分小测和工图期末所以没有进行。

树的直径和重心

林星涵：

陶吟翔：[FJOI2014]树的重心

传送门

题目大意：给出一棵有$n$个节点的树，问有多少个联通子树和这棵树的重心相同。

数据范围：$n \le 200$，多组数据。

解题思路：首先用$O(n)$的时间求出重心，由于要计数所以我们考虑DP。一棵树有可能有一个或两个重心。如果有两个重心，说明无论以哪个为重心，子树的构成都是一样的，所以如果要选一个联通子树使重心与原来相同，必须在这两个重心的子树上选同样多的点。令$f_{u,i}$表示在子树$u$里选$i$个点且包括$u$的方案数，那么有$f_{u,i}=\sum_{v \in son_u} \sum_{j=1}^{min(i-1,size_v)} f_{u,i-j} \times f_{v,j}$。答案为$\sum_{j=1}^{min(size_{g_x},size_{g_y})} f_{g_x,i} \times f_{g_y,i}$。如果只有一个重心，说明我们选的子树的最大值不能超过总数的二分之一，我们先算出$f$的值，然后定义$F_{i,j}$为选了$i$个点，最大子树为$j$个点的方案数，初始有$F_{i,i}=\sum_{v \in son_g} f_{v,i}$。随后对于$1 \le k \le i$，有$F_{i,max(j,k)}+=F_{i-j,k} \times f_{v,j}$。答案为$1 + \sum_{i=1}^n \sum_{j=1}^n [2j \le i]F_{i,j}$。

郭衍培：