ddcc

AT_ddcc2020_final_d Pars/ey 重工业题。 找环然后树形 DP 是显然的，先考虑断开环上的边怎么做。 把环复制一遍放在结尾，记 \(sum_i\) 为环长的前缀和，\(f_i\) 为该子树内的最长根链的长度，问题变为每次给定一个区间，要求找到 \(i,j(i>j)\) 使得 ......