这题 换根dp+倍增。

板子是绿，但是这很不板，有点思维难度。

或者用树链剖分也可以做，但是这板子已经是蓝了 而且码量不小。

思维绿，换根绿，码量蓝，综合来看蓝比较合适。