rt，理由如下：

1. 换根 dp 的板子题是绿；

2. 这道题还需要用到倍增 lca 或树剖等做法，并且需要熟练掌握树上倍增，这里至少也是绿的难度。

综上，建议升蓝。