这个题数据水完了，建议大家自己自己随便拍两组，可能要比给的数据强。

有一个简单的做法，注意到对于一个节点 $u$，和他子树内所有关键点构成的集合 $S$，要么是 $u$ 能到达 $S$ 中的一些点，要么是 $S$  的一些点能到达 $u$，或者 $u,S$ 之间不连通。

直接设 $f_{i,0/1/2}$ 表示上面三种情况，做一个树上背包的合并即可，复杂度应该是 $O(n)$。

一个细节问题是对于关键点 $x$ 其 dp 的初始值如何处理，做法很多，但都能做到 $O(n)$。反正我写的很屎，但是 fhx 提供的很简洁（遗憾的是我没有理解）。

其实最开始我是往连通性方面想的 dp，结果最后想到了状态压缩上（？），于是在写错了一个很难写代码后，我短暂思考了另外一种很繁琐的做法，就是容斥。

先将边任意定向向都视为合法，然后减掉不合法的方案数，注意 $x\to y$ 和 $y\to x$ 这两种关系是不一样的，所以不合法的条件一共有 $k(k-1)$ 种。

枚举 $S$，求至少满足 $S$ 中所有不合法条件的方案数 $f(S)$，答案是 $\sum_{S}(-1)^{|S|}f(S)$，问题变成如何求答案。

暴力求是不行的，考虑树链剖分后用线段树维护，变成一个链覆盖的问题，可以做到 $O(k^2\log^2 n)$，最后的复杂度就是 $O(4^kk^2\log^2n)$，实际上因为复杂度省略了常数，容斥在 $k\le 4$ 的条件下可以轻松通过。

因为我用新加的数据测试了之前错的代码，所以给出的代码不保证对，但是这份代码是 fhx 的，应该是对的。