对于前两个任务随便做。
对于第一个任务\(dfs\)一遍即可。（但也可以是度数为奇数的点的个数）
对于第二个任务显然可以二分然后在保证任务一的情况下判断。
对于第三个任务，可以树形\(DP\)处理。考场的时候想到设\(f[i][j]\)表示\(i\)连向父亲一条长度为\(j\)的边的方案数。但是转移的时候时间复杂度似乎会超，所以当时没有细想。
但是现在看来，在度数\(<=16\)的情况下，我们似乎可以用集合的办法来处理问题。考虑设\(g[S]\)表示集合\(S\)的儿子相互成边且合法的方案数。考虑最后是否还会剩下一条边。
然后通过\(g\)和\(f\)来转移给父亲节点即可，时间复杂度为\(O(n*(2^d+n*d))\)。
考虑优化，我们可以用线段树来存储\(f\)，然后用长链剖分的思想来让\(x\)节点直接继承重儿子的\(f\)，然后再添加轻儿子，这样来保证时间复杂度。
具体而言，就是先求\(g\)，对于求\(g\)时候的处理合并两个儿子的答案的时候，考虑把\(mxdep\)小的暴力取出，然后对另一个儿子线段树区间查询贡献即可。
而对于之后求\(x\)的\(f\)的话，我们先分儿子个数为奇数还是偶数两种情况来处理，为偶数的话还要考虑伸上去的长度为\(1\)的情况。
而对于其他情况，都是考虑选择偶数点（剩下\(1\)到\(2\)个）。
#include<to be done>
gmoj 7017. 2021.03.15【2021省赛模拟】B
原文：https://www.cnblogs.com/jz929/p/14548709.html