P11363
1~3 写你喜欢的暴力，期望得分12pts。
18~21 手玩一下链和菊花，结论懒得摆了，期望得分28pts。
4~6 好我们开始详细解说。
首先如果你真的想不到题解做法的话，可以写一个换根dp，过程就比较的繁琐，这里就不赘述了。
然后你发现，每个原树节点对应的所有边在新树上对应一条链，链下挂着许多棵子树。而你钦定了根关键边后，每个点的入边是确定的，唯一需要确定的是其他关键边的顺序，所以设每个点的度数为d
u
，那么答案为∏
u=1
n
(d
u
−1)!，好好理解一下，期望得分40pts，是这题的大众分，然而captainOI并没有拿到。
7~10 k=2也是比较重要的一个部分分。我们用k=1的答案乘2，减去这两条边都可行的情况。显然，我们可以画出这两条边在树上构成的链。在链上的点(不算链端点)，它的入点和出点都被确定(好好想想),所以减去部分为∏
u=1
n
(d
u
−1)!×∏
u∈S
(d
u
−1)
−1
，其中S为链上点的集合，期望得分56pts。
11~12 考虑容斥，可以发现，能作为根的边在原树上一定构成一条链。所以枚举点集，找出链，像k=2一样计算答案即可，复杂度O(n2
k
)，期望得分64pts。
13~15 还是容斥，设f
i
表示钦定i条关键边作为根的方案数，答案即为∑
i=1
k
(−1)
i−1
f
i
。枚举两条边l1和l2，按k=2算出的答案为ans，设l1和l2之间有v条关键边(包括l1和l2)。那么ans对f
i
的贡献即为(
i−2
v−2
)ans，复杂度O(nk
2
)，期望得分76pts。
16~17 实现要精细，实现枚举l1算出所有l2，可用换根dp实现，注意去重，复杂度O(nk)，期望得分84pts。
22~25 大决战，发现其实如果v≥3，那么这个ans对答案的总贡献为0。所以只需要用k=1的答案乘k，再减掉l1和l2中间没有关键边的方案数即可，可用换根dp实现，注意去重，复杂度O(n+k)，期望得分100pts。
其实换种理解方式，一种链上含S条关键边的方案，会被加上S次，再被减掉S−1次，故这样的容斥是正确的。而且如果直接想到这里，就可以愉快地切掉T3，为后面的T4和前面的T1留出宝贵的时间了。
最后来一句，相信NOIP，能力到了，就一定能考出来！