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

树的直径和重心

林星涵：

陶吟翔：[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}$。

郭衍培：

题目链接

题目大意：给定一个长度为n的序列A，一个长度为m的序列B。保证B序列单增。将A分成m个子串，满足第i个子串最小值为$b_i$。求满足要求的划分方案。

数据范围：$n,m\le 2\times 10^5$

解题思路：要利用好B单增的性质。维护一个后缀最小$c[i]=\min^{k=i}^na[i]$。