2021上海ICPC Edge Groups

ac.nowcoder.com/acm/problem/231126

题意： 给你一颗树，要求对  条边两两分组，每组有一个公共节点，求方案数

思路：对于节点 ，如果有偶数条边与其相连，那么可以进行两两分组，如果只有奇数条边，那么两两分组之后必然剩下一条边没有被分组，此时就需要一条   (为的父节点) 边来与这条剩下的边匹配

因此，对于  的子节点 

•  如果对  有贡献的边数为偶数个，那么 节点对  节点也是有贡献的，即  这条边是加入计数的

•  反之，   这条边是要加入对   的贡献的，则不计入   中

对于每个节点，如果其有贡献边数是偶数，就两两分组，如果是奇数，那么加上一条与父节点相连的边就变成偶数了

所以问题转化为 条边中两两组合有多少种方案数，计算方式为：

化简为：

如何计算贡献边呢？

显然是一个递归问题，考虑树形dp，定义表示以为根节点的树可以产生多少种方案数，所以根据乘法原理，