20170630总结

今天是的第二天，主讲树形，题目较难。早上考试，看到题目有些难，想做快些，结果把题意看错，得不偿失。也因此没有时间把记忆化改为。不过的确很难，是著名的鹰蛋问题。这道题的正解很有意思，有时间可以写一写。下午是树形的讲解，复习了经典的找直径、重心和“没有上司的舞会”这一经典题目。随后“创世纪”一题将“没有上司的舞会”拓展到基环树上。接着是的一道比赛题，因为没有怎么接触过树上背包，对此类问题有些生疏，故听得有些朦胧。树形后，又将了中的。此类问题和树形差不多，只是根据题意有所区别，更为灵活。最后讲了问题，即构造一个无向图使每个点度为，且有一个桥。在此给出构造方法（复习一遍，加深印象）：若为偶数，则无解。若为奇数，先构造一个个结点的完全图，节点编号为，接着删去到这些边，每个点的度都为了。然后再新建个点，分别向原来的个点连线，于是原来的个点度都为，个新点度都为。在这三个点中任选两个相连。现在把整个图复制一遍，变为两个图，把这两个图中度为的两个点连起来，这样就有桥了。今天的题目整体较难，得写一些以加深印象。