题解 P2024 【食物链】

· · 题解

我来讲一下那个合并时计算原来两根距离表达式的推导方法。

设合并后两根距离为a(即要求的量）

R[i]表示点i到他们原来祖先的距离，途中所有线段长都可以表示。

注意每条边的长度是不一样的，∴R[x]+a-R[y]≠R[x]，而等于x、y的距离即食物关系（大家可以往下翻，下面有关于这个的讲解）

设该距离为t

方程：R[x]+a=t+R[y]，整理得a=t-R[x]+R[y],当然把x与y换一下也是成立的，这取决于你的程序。

剩下的前人都讲过了，再次我都不赘述了。