103470g

树上区间dp。 由于dp转移跟左右端点有关，考虑怎样转移端点。 左右端点只有被染色了才能被转移，那就多记个两维，表示左右端点是否已经被染色就好了。 $dp_{u,v,t,0/1,0/1}$ 表示左右端点 $u$，$v$ 当前已经染了 $t$ 个点，左右端点染色四种情况的路径长度。 ```cpp #i ......