突然发现两天其实 T1 非常不简单。
请问大佬们 Day1 T1 的结论是怎么证的吗?
以及 Day2 T1 我的做法大概是这样:
特判 n≤3 的情况。
令下面过程为 F(a,b,c):找到 dis(a,b)+dis(b,i)+dis(i,a) 最大的 i,然后 c←i。
初始 a=1,b=2,依次进行 F(a,b,c),F(a,c,b),F(b,c,a)。
然后判一下。
感觉这样做完之后,a,b,c 两两之间的路径,必然有一条是直径,但是没想出什么证明方法,请问有大佬能证明一下吗?谢谢啦。
以及往昔重现:最后发现自己是被结论题搞崩了。