• 创建了本周训练周报
• 创建了暑期牛客第九次集训界面
• 创建了暑期牛客第十次集训界面

2020牛客暑期多校训练营（第九场）
2020牛客暑期多校训练营（第十场）

fyh:
题目大意：给一个无向图，你要不在图中找到一个长度大于等于$\lceil \frac{n}{2} \rceil$ 的简单路径，要不就找若干个二元组（其中这些二元组的元素不能重复，至少要多于等于$\lceil \frac{n}{2} \rceil$ ），使得任意两个二元组组成的子图，至多有两条边。
tag:dfs树，构造
做法:随便找一点开始求他的dfs树，如果dfs树中有深度大于等于$\lceil \frac{n}{2} \rceil$ 的点，就直接输出即可，否则就找所有深度相同的点，两两配对，一定能保证配出$\lceil \frac{n}{4} \rceil$ 对。怎么证明呢？ 先证这任意两个二元组组成的子图吧，根据dfs树的性质，所有非树边一定是祖先连往子孙，不可能存在子树之间的连边 ，深度相同的点显然是属于两个子树，所以保证两个二元组$(a,b),(c,d)$ 其中$deep[a]=deep[b],deep[c]=deep[d]$ 令$deep[a]<deep[c]$，a和b 不可能连边，c和d不可能连边，那两条边只可能是a和c，b和d为父子关系的时候才可以算上。 再证一定大于$\lceil \frac{n}{4} \rceil$ 对，因为不存在深度大于$\lceil \frac{n}{2} \rceil$ 了，所以最大深度不过$\lceil \frac{n}{2} \rceil$ ，每一个深度只有当有0个或者1个节点的时候才会放弃这个深度，根据抽屉原理一定能选出$\lceil \frac{n}{4} \rceil$ 对满足。
comment:虽然这题出的有点强行，但是利用dfs树的一些性质还是十分巧妙

wxg:
题目大意：
tag:
做法:
comment:

hxm:
题目大意：
tag:
做法:
comment:

比赛：Codeforces Round #663 (Div. 2)
补第九场J 第十场J 整理了树上哈希的板子