ZJOI2012

[ZJOI2012]灾难

倍增/link-cut 动态维护LCA
注意到如果构造出一个表示灭绝关系的树,那么树上的前向边的多少对答案以及结构是没有任何影响的。
最后DFS求一下子树大小即可。

[ZJOI2012]网络

link-cut tree找根
动态维护图(实质是一条链)的连通性

[ZJOI2012]波浪

这是神DP(与SRM489的Apple tree类似)
F[i,j,k,s]表示按照从小到大的顺序把1-i都放置完毕后累计的和是j目前有k个独立块且边界独立块的个数为s的排列数量。
转移分为合并两独立块、在一个独立块后追加元素、新增一个独立块三类,分类讨论即可。

这题需要和BSOJ3070 Emotional Skysraper类比。这题状态设计的思路是寻找前i项满足如此大小关系的排列数量,去冗便可得到状态了。