https://codeforces.com/contest/916/problem/E

题意：

有一棵n个点的树，每个节点上有一个权值wi，最开始根为1号点．现在有3种

类型的操作：

• 1 root, 表示将根设为root.

• 2 u v x, 设u, v的最近公共祖先为p, 将p的子树中的所有点的权值加上x.

• 3 u, 查询u的子树中的所有点的权值和．

对于类型3操作，输出答案．

题解：

线段树 + 树链剖分

树链剖分的意义在于：由于函数

int lca(int x,int y)

大量使用，如果不使用树链剖分，当树退化为一根链时，

int lca(int x,int y)的复杂度为O(n), 从而整个算法的复杂度为O(n^2)

使用树链剖分时，整个算法的复杂度为O(nlogn)

该程序的关键点是：

不实施换根，每次只记录新根，并注意新根在后续操作的影响。

主要难点：在不同新根位置下，求包含x，y 的最小子树的根节点