偶然看到一道题:
给定一棵树,树中包含 n 个结点(编号1~n)和 n−1 条无向边,每条边都有一个权值。
请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。
1≤n≤3∗104
我的思路类似次小生成树,先记录在自己儿子内的最长链和次长链以及最长链经过子结点的编号,然后分类讨论其他辈;
如果是父亲/直系祖宗,需要存储原来的节点向上的最长链,判断其父亲 的 儿子 的最长链是否是自己,如果是则使用次长链,不是则使用最长链,然后遍历这个父亲的其他儿子;
最后遍历节点并输出,如果是叶子节点则输出向上的最长链,不是则输出向下最长链与向上最长链的最小值。
但是这个做法可以被下面这张图 hack 掉(?)
对于这个节点,他的父亲的最长链有自己,次长链也有自己,但还是会取次长链!
但是如果维护节点从大到小每一条链,空间会炸裂!如果每次维护父亲节点时重新搜索,会跑的很慢,各位神犇可不可以指出我思路的错误,或者提供对于这个数据更好的解题方法?
口胡了一份代码,可以更好的了解思路,但是有些问题(总是输出 0 (((:Link