萌新再次求助 PKUWC
  • 板块学术版
  • 楼主recollect_i
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/1/19 20:32
  • 上次更新2025/1/20 08:24:38
查看原帖
萌新再次求助 PKUWC
636142
recollect_i楼主2025/1/19 20:32

突然发现两天其实 T1 非常不简单

请问大佬们 Day1 T1 的结论是怎么证的吗?

以及 Day2 T1 我的做法大概是这样:

特判 n3n \le 3 的情况。
令下面过程为 F(a,b,c)F(a, b, c):找到 dis(a,b)+dis(b,i)+dis(i,a)dis(a, b) + dis(b, i) + dis(i, a) 最大的 ii,然后 cic \gets i
初始 a=1,b=2a = 1, b = 2,依次进行 F(a,b,c),F(a,c,b),F(b,c,a)F(a, b, c), F(a, c, b), F(b, c, a)
然后判一下。

感觉这样做完之后,a,b,ca, b, c 两两之间的路径,必然有一条是直径,但是没想出什么证明方法,请问有大佬能证明一下吗?谢谢啦。

以及往昔重现:最后发现自己是被结论题搞崩了。

2025/1/19 20:32
加载中...