• 创建了本周训练周报
• 创建了暑期自己第一次加训界面

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序列的板子

复习了回文自动机，整理字符串模板

复习了点分治，整理了点分治模板