换根 DP

二次扫描：固定根一遍 DFS，再一遍换根 O(1) 推每个点。