Warning: session_start(): open(/tmp/sess_682000d50de87d3501071303eaf15434, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/8/8fe637ac40e9dfa91f93fbcd08d065e4.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 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序列的板子
----
====== 王兴罡 ======
复习了回文自动机,整理字符串模板
----
====== 黄旭民 ======
复习了点分治,整理了点分治模板
\\