Codeforces Round #721 MEX Tree 题解 (Java/C++)

题意

给你一颗树。现在对于任意的k，问你有多少对u,v使MEX(u,v)=k。其中MEX是说，这两个点之间的最短路的所有点的下标中第一个没有出现的数。

题解

以0做树根。DFS统计每个节点的子节点（包括自己）总数，记为count。

对于k=0就很显然。也就是只要不经过树根即可。那么显然结果是$\sum_{child}{C_{child.count}^2}$。

对于k=1。就是一定要经过树根，且不经过1。那么任意一条边，直接和其他的任意点匹配即可。

对于其他情况，显然u和v构成的路径必然覆盖0-(k-1)中的所有点。也就是说，如果一旦0-(k-1)存在分支，那么后面就一定都是0。

于是在1之后，我们维护这个链的两端。每次都是从两端出发各自选一个点组合起来即可。

代码

Java

C++