Problem F. Moles
Brief description:
… 动态维护一棵边权树, 支持单边修改。。(边权可以是负数)。。
。。以及询问两点之间的路径长度,询问某点到期子树内一点的路径长度的最大值。
Analysis:
… DFS 一遍。。得到。。
一个 Euler 序。。用来求 LCA 。。。
一个一进一出的 DFS 序 用来维护路径。。
。。需要区间求和、和区间求最大前缀和两类操作。。
。。这里我们选择线段树。
。。。线段树做第二问。。树状数组做第一问。。
。。线段树同时解决两问。。