- P6419
- 这是一道很明显的 换根DP
- 我们发现 \(x\) 点的答案很明显是由需要经过的边乘 2 再减去从 \(X\) 开始的一条最长链
- 我们先考虑所有边乘 2 的事
- 定义 \(f_x\) 为在以 \(x\) 为根的子树中需要经过的边乘 2 的答案，\(len_x\) 表示在以 \(x\) 为起点的最长链的长度，\(slen_x\) 表示以 \(x\) 为起点的次长链的长度，\(id_x\) 是 \(x\) 要找到一条最长链第一步要到的节点
- 接下来就是换根分类讨论了大致分为
- 所有的 \(K\) 个节点都在以 \(x\) 为根的子树内的
- 所有的 \(K\) 个节点都在除以 \(x\) 为根的子树外
- 其他情况
