发现一个巨大无比爆炸重要的性质。树上路径 MEX 只有 0,1,2 三种情况/dy。
想了会交替染色为何不对，发现对于单点填 0 会有 1 的贡献，而填 1 没有贡献。所有交替染色只能保证长度 \(\ge 2\) 的路径的权值和最大。
最优化可以考虑上下界。先钦定答案为上界 \(n(n+1)\)，即每条路径 MEX 都为 2。虽然显然取不到。
答案为 \(n(n+1)-c1-2\cdot c0\) 其中 \(c1\) 为 MEX 为 1 的路径数，\(c0\) 为 MEX 为 0 的路径数，发现 \(c0,c1\) 与 \(0,1\) 的极大连通块有关，一个大小为 \(siz\) 的极大连通块可以贡献 \(\frac{siz(siz+1)}{2}\) 条路径，现在就是要考虑最小化 \(c1+2\cdot c0\)。于是设计状态 \(f_{u,i,0/1}\) 表示以 \(u\) 为根的子树，\(u\) 在大小为 \(i\) 的 \(0/1\) 的极大连通块中。