题意
进行以下操作，维护树结构：
- 换根
- 查询 LCA
- 子树加
- 查询子树和
$1 \leq n, m \leq 10^5$
题解
首先你需要会 这个。
这题跟 P3979 遥远的国度 唯一的区别就是要求个 LCA 嘛。
但其实你会发现这个操作毫无难度。
我们开局的时候随便选一个点把树剖了，然后看怎么应付操作。
假设当前根为 $r$。
我们记 $\mathsf{LCA}'\left(u, v\right)$ 表示以 $r$ 为根时的 LCA。$\mathsf{LCA}\left(u, v\right)$ 为以树剖时的根为根时的 LCA。
当前树中的 $\mathsf{LCA}'\left(u, v\right)$ 其实就是 $\mathsf{LCA}\left(u, v\right), \mathsf{LCA}\left(u, r\right), \mathsf{LCA}\left(v, r\right)$ 中深度最大的那个。
结论来源于分讨，喜欢讨的自己去讨。
代码
/* Please submit with C++17! It's best to use C++20 or higher version.
* No header file and no RBLIB (https://git.rbtr.ee/root/Template).
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* I've reached the end of my fantasy.
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#ifndef XCODE
constexpr bool _CONSOLE = false;
#else
constexpr bool _CONSOLE = true;
#endif
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#define FULL(arg) arg.begin(), arg.end()
#define dor(i, s, e) for (tp i = s, $##i =(s)<(e)?1:-1,$e##i=e;i!=$e##i;i+=$##i)
#define gor(i, s,e)for(tp i=s,$##i=(s)<(e)?1:-1,$e##i=(e)+$##i;i!=$e##i;i+=$##i)
// :/
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
struct SEG {
struct S {
tp sum, len;
S() = default;
S(tp sum, tp len) : sum(sum), len(len) {}
};
static S op(S l, S r) { return S(l.sum + r.sum, l.len + r.len); }
static S e() { return S(0, 0); }
static S mapping(tp tag, S dat) { return S(dat.sum + tag * dat.len, dat.len); }
static tp composition(tp tag1, tp tag2) { return tag1 + tag2; }
static tp id() { return 0; }
};
tp n, m; bin >> n >> m;
vetp a(n + 1); bin.rar(1 + FULL(a));
vetp dep(n + 1);
vetp f(n + 1);
vetp hson(n + 1);
vetp s(n + 1);
vetp top(n + 1);
vetp dfn(n + 1);
vetp lst(n + 1);
vetp real(n + 1);
vector<vector<tp>> e(n + 1);
for (tp i = 1; i < n; ++i) {
tp u, v; bin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
lib::Segtree<SEG::S, SEG::op, SEG::e, tp, SEG::mapping, SEG::composition, SEG::id> o(n + 1);
auto dfs1 = [&](auto $, tp x) -> void {
dep[x] = dep[f[x]] + 1;
s[x] = 1;
for (auto& i : e[x]) {
if (i == f[x]) continue;
f[i] = x;
$($, i);
s[x] += s[i];
if (s[i] > s[hson[x]]) hson[x] = i;
}
};
tp cnt = 0;
auto dfs2 = [&](auto $, tp x, tp h) -> void {
real[lst[x] = dfn[x] = ++cnt] = x;
top[x] = h;
if (!hson[x]) return;
$($, hson[x], h); lst[x] = lst[hson[x]];
for (auto& i : e[x]) {
if (i != f[x] && i != hson[x]) { $($, i, i); lst[x] = lst[i]; }
}
};
auto LCA = [&](tp x, tp y) -> tp {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) x = f[top[x]];
else y = f[top[y]];
}
return dep[x] < dep[y] ? x : y;
};
auto get = [&](tp x, tp y) -> tp {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
if (f[top[x]] == y) return top[x];
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
return hson[x];
};
auto get_lca = [&](tp x, tp y, tp r) -> tp {
tp c1 = LCA(x, y), c2 = LCA(x, r), c3 = LCA(y, r);
if (dep[c1] >= dep[c2] && dep[c1] >= dep[c3]) return c1;
if (dep[c2] >= dep[c1] && dep[c2] >= dep[c3]) return c2;
return c3;
};
dfs1(dfs1, 1);
dfs2(dfs2, 1, 1);
gor(i, 1, n) o.set(dfn[i], SEG::S(a[i], 1));
tp r = 1;
gor(i, 1, m) {
tp op = bin;
if (op == 1) r = bin;
else if (op == 2) {
tp u, v, k; bin >> u >> v >> k;
tp x = get_lca(u, v, r);
if (x == r) o.apply(1, n, k);
else if (dfn[r] > dfn[x] && dfn[r] <= lst[x]) {
tp t = get(x, r);
o.apply(1, dfn[t] - 1, k);
o.apply(lst[t] + 1, n, k);
} else o.apply(dfn[x], lst[x], k);
} else {
tp x = bin;
if (x == r) bin << o.all_prod().sum << '\n';
else if (dfn[r] > dfn[x] && dfn[r] <= lst[x]) {
tp t = get(x, r);
bin << o.prod(1, dfn[t] - 1).sum + o.prod(lst[t] + 1, n).sum << '\n';
} else bin << o.prod(dfn[x], lst[x]).sum << '\n';
}
}
return 0;
}
void MIST() {
}
// :\ */