2018-Reconquista-T54
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Contest Information ==
''' Petrozavodsk Winter 2012 - Tokyo Kroliki Contest '''
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001397 Opentrains]
== 流水账 ==
== 总结 ==
=== lsmll ===
H卡的太伤了，我应该早点提出那种简单的DP，虽然是错的，不过经过jsb修补后就过了。然后B题我们没有想出来最重要的性质，F题没看出来最多只有2n-2条边，只能说水平不够，还需提高。
=== jsb ===
前期还行，中后期就爆炸了。[[br]]
主要是被一道数量还行但是通过率比较低的H卡住了。[[br]]
我和威威思考得太久了，后来各种想歪，想到了很复杂的地方去了。[[br]]
最后经lsmll学长提醒后发现一个简单的做法，但是还是WA。[[br]]
无奈之下疯狂对拍，才一点一点fix完，导致后来B题和F题没时间做了（好像本来也不太会呜呜呜）。
=== lzw ===
H题卡的太久了，看到通过率不高，就往复杂的方向去想了。B题一直没有从度的方向考虑，锻炼思维的题目还是要多做。
== 补题 ==
A []
B [lzw,lsmll]
E []
F [lsmll]
I []
== 题解 ==
B,H[https://www.cnblogs.com/jiangshibiao/p/8955409.html 6.3处]
[B by lzw] 首先证明联通块内任意两点之间的距离不会超过2. 考虑u->v的一条路，假设长度>=3, 那么路径上一定存在四个点a->b->c->d, a->c有边或者b->d有边。可以让路径长度缩小1，不断缩小长度可以<=2。然后可以证明每个联通块，度数最大的点一定和其他所有点都有边。证明太难表述了QAQ，大致是随便先选一个点，然后联通块分为2层，第1层是和它距离为1的，第2层是距离为2的，如果1层的某个点和2层的某个点有边，那么它和1层的所有点有边。所以度数最大的点一定是在和第2层有边的点里。 假设存在2层的某个点和它没边，反证这个图可以继续加边即可。 所以如果一个点的度比它相邻的点度数大，直接删去就好，选它肯定不优。 剩下的就是一些团了。大小乘起来就是方案数。
[B by lsmll] B题的另一种做法：记N(u)为所有与u的相邻点加上u本身的集合，则可以证明对于任意两个有边相连的点u,v，必然N(u)包含N(v)或者N(v)包含N(u)，具体是哪一种情况只要看哪个点读数大即可。因此，对于每一条边，不选度数较大的点一定严格优于不选另一个点。所以，对于每条边给两端两个点中度数较大的打个标记，一样的度数时给编号大的打标记。则最后独立集大小即为没有被打标记点的个数。方案数为每个没有被打标记点u的N(u)中度数与u相同的点个数乘积。
[F by lsmll] 可以用数学归纳法证明边数不超过2n-2，所以只有2n-3和2n-2两种。从证明过程中又可以推出2n-2必然是双向边的“树”，而2n-3时是一些公用一条边的三元环加“树”。所以枚举三元环个数，再DP一下剩下点分配到环上的点的方案数即可。Contest Information
Petrozavodsk Winter 2012 - Tokyo Kroliki Contest
流水账
总结
lsmll
H卡的太伤了，我应该早点提出那种简单的DP，虽然是错的，不过经过jsb修补后就过了。然后B题我们没有想出来最重要的性质，F题没看出来最多只有2n-2条边，只能说水平不够，还需提高。
jsb
前期还行，中后期就爆炸了。[[br]]
主要是被一道数量还行但是通过率比较低的H卡住了。[[br]]
我和威威思考得太久了，后来各种想歪，想到了很复杂的地方去了。[[br]]
最后经lsmll学长提醒后发现一个简单的做法，但是还是WA。[[br]]
无奈之下疯狂对拍，才一点一点fix完，导致后来B题和F题没时间做了（好像本来也不太会呜呜呜）。
lzw
H题卡的太久了，看到通过率不高，就往复杂的方向去想了。B题一直没有从度的方向考虑，锻炼思维的题目还是要多做。
补题
A []
B [lzw,lsmll]
E []
F [lsmll]
I []
题解
B,H6.3处
[B by lzw] 首先证明联通块内任意两点之间的距离不会超过2. 考虑u->v的一条路，假设长度>=3, 那么路径上一定存在四个点a->b->c->d, a->c有边或者b->d有边。可以让路径长度缩小1，不断缩小长度可以<=2。然后可以证明每个联通块，度数最大的点一定和其他所有点都有边。证明太难表述了QAQ，大致是随便先选一个点，然后联通块分为2层，第1层是和它距离为1的，第2层是距离为2的，如果1层的某个点和2层的某个点有边，那么它和1层的所有点有边。所以度数最大的点一定是在和第2层有边的点里。 假设存在2层的某个点和它没边，反证这个图可以继续加边即可。 所以如果一个点的度比它相邻的点度数大，直接删去就好，选它肯定不优。 剩下的就是一些团了。大小乘起来就是方案数。
[B by lsmll] B题的另一种做法：记N(u)为所有与u的相邻点加上u本身的集合，则可以证明对于任意两个有边相连的点u,v，必然N(u)包含N(v)或者N(v)包含N(u)，具体是哪一种情况只要看哪个点读数大即可。因此，对于每一条边，不选度数较大的点一定严格优于不选另一个点。所以，对于每条边给两端两个点中度数较大的打个标记，一样的度数时给编号大的打标记。则最后独立集大小即为没有被打标记点的个数。方案数为每个没有被打标记点u的N(u)中度数与u相同的点个数乘积。
[F by lsmll] 可以用数学归纳法证明边数不超过2n-2，所以只有2n-3和2n-2两种。从证明过程中又可以推出2n-2必然是双向边的“树”，而2n-3时是一些公用一条边的三元环加“树”。所以枚举三元环个数，再DP一下剩下点分配到环上的点的方案数即可。