CodeForces-379F New Year Tree

发表于 | 分类于
字数统计: 191 | 阅读时长 ≈ 1

题目大意：
初始时有一棵4个节点的三叉树
每次操作在一个叶子节点下面加入两个节点
问每次操作完树的直径

设当前树的直径为S-T
每次加入节点后，树的直径至多只会改变一个端点，另一个节点仍是S 或T

证明如下

  • 考虑加入节点x 的父节点$x_{fa}$，在x 未加入时，根据直径的求法，离$x_{fa}$最远的点一定是S 或T
  • 再加入x 后，易得离$x_{fa}$最远的点还是S 或T，因此离x 最远的点也是S 或T

因此每次求一遍x 到S，T 的距离，若大于S-T 就更新

代码就不放了