竹子听

4月7日晚饭后 终于看懂了看了一个中午的这道题

LCA:NOIP DAY1 T2 天天爱跑步

我中午看的时候居然十分懵圈，唉为什么我这么傻呢

就是很明显的将路径分成上下两段，S->LCA(S,T)和LCA(S,T)->T

就说说第一段怎么求，第二段也是类似的。

若设LCA(S,T)=i

由题意我们可以得到，deep[s]-deep[i]=w[i]

移项后，我们可以得到 deep[s]=deep[i]+w[i]

因为deep[i]和w[i]都是已知的，我们可以设为k[i]

对于每个节点，我们先递归访问它的所有子节点

求它儿子节点里，有多少个的deep=ki，

如果每一个都访问一遍，显然就太慢了，

所以用一个桶记录子节点里面有多少个节点的deep[]=k[i]，加起来

这里还有一个问题，就是如果我们优先遍历它的左儿子，

那我们对右儿子的操作必然受影响，

只要我们求一下进入前和进入后的的差值，就可以完美的解决这个问题了

然后求下降的，也是一样的。