题意：给定一棵 个节点的树，保证 为偶数。
给树上的点两两配对，对于一对 ，在树上将 的路径染色。
定义一个配对方案合法当且仅当所有边都有颜色。求合法配对方案数，答案对
取模。
，时限 。
不难想到如下 ：
表示 子树内剩余
个节点没有匹配，且匹配路径以及未匹配点到 的路径覆盖整个子树的方案数。
边界：
转移：
复杂度为 。
以上
难以优化，改而考虑容斥。
钦定边集
不能被覆盖，设方案数为 ，则贡献为
。
考虑钦定边集 后如何计算
。将不能被覆盖的边断掉，每个连通块内都能任意匹配，对于一个大小为 的联通块，方案数即为 ，若 为奇数方案为
。
于是，记 表示 子树内断边之后 所在的联通块大小为 的贡献总和。
记 为 子树内的方案数。
边界：
转移：
其中，
是断边的贡献，后者是不断边的贡献。
最终答案即为 。
根据树形背包，复杂度为 。