====== Update on Wiki ======
   * 创建了本周训练周报
   * 创建了暑期自己第一次加训界面

----

====== 团队训练 ======
[[front_page_SummerTrain13|2019 Multi-University Training Contest 2]]

----

====== 每周推荐 ======
**fyh:**
\\ **题目大意：**定义一个无根树的权值为所有点的度数的平方的和，求有标号的$n$个点形成的所有森林的权值的和。
\\ **tag:**prufer序列，计数问题
\\ **做法:**设$f[i]$表示$i$个带标号的节点有多少种不同的森林，递推式为$f[i]=\sum_{j=1}^i C_i^j*f[i-j]*j^{j-2}$。

设$w[i]$表示$i$个点能形成的所有无根树的权值和,考虑每一个点以及不同的度数对答案的贡献，递推式子为：$w[i]=i*\sum_{d=1}^{i-1}d^2*C_{n-2}^{d-1}*(n-1)*(n-2-(d-1))$

那么最终答案$ans[i]$就是$ans[i]=\sum_{j=1}^iC_i^j*(j^{j-2}*ans[i-j]+f[i-j]*w[i])$
\\ **comment:**prufer序列一定要单独讨论N=1,N=2的情况，另外多开longlong取模会导致常数巨大

**wxg: **
\\ **题目大意** 给了一个字符串，问你有多少子串，自身是回文串而且一半也是回文串
\\ **tag: ** 回文自动机
\\ **做法:**  由回文自动机的性质知道一个串的本质不同的回文串最多有 $n$ 个，我们可以用回文自动机统计不同回文串的个数并标记位置，之后枚举每个串并用哈希判断他的一半是不是回文串就行
\\ **comment: **  需要发现本质不同的回文串个数最多为串的长度

**hxm:**
\\ **题目大意：** 给一棵树，每个点都有一种颜色，设$s(i,j)$为两点之间颜色种类数，求所有点对$s(i,j)$之和
\\ **tag:** 点分治，差分
\\ **做法:**
点分治即可

对于每棵分治出来的树，考虑过根的所有路径对树内点的影响
首先单独考虑一种颜色的影响，从根节点出发到每棵子树的每个点u，u节点在该颜色下会产生贡献当且仅当u到根的路径上有该颜色的节点
所以我们只要找出一个子树中所有颜色为该颜色，且其祖先中没有该颜色【也就是最高的该颜色点】，其子树所有点都会产生贡献，那么所有的对根的贡献就是所有这样点的子树大小之和

考虑对子树内的点，就减去该子树的贡献，就转化为和根类似的了
每当第一次经过一种颜色的点时，其子树内所有点经过该点必定产生该颜色的贡献，此时把该颜色的贡献改为剩余子树的大小即可

还有，根节点的颜色特殊考虑

写起来细节真的多

\\ **comment:** 点分治练习

----

====== 个人训练 ======

====== 傅云濠 ======
比赛：educf#93(ABCD),abc175(ABCDE),cfglobal#10(ABCDE),topcoder???(打了个寂寞)
\\ 补第七场I，并做了一些有关prufer序列的题
整理了构建prufer序列的板子
----

====== 王兴罡 ======
复习了回文自动机，整理字符串模板
----

====== 黄旭民 ======
复习了点分治，整理了点分治模板
\\