传送门
Luogu
解题思路
带换根操作的树剖。
换根只会影响更新或查询子树信息的操作。
我们始终保持初始的根不变，然后只要分类讨论一下：
假设当前被查询的节点是 (u)
- 如果 (u) 就是根节点，直接询问整棵树；
- 如果 (u) 不是根，且不是初始根的祖先，直接查询子树即可；
- 如果 (u) 是根的祖先，那么我们就找到 (u) 到根这条路径上的第一个儿子，然后分开查询即可
至于怎么分开查询，自己yy一下就好了。
细节注意事项
- 咕咕咕
参考代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
using namespace std;
template < typename T > inline void read(T& s) {
s = 0; int f = 0; char c = getchar();
while (!isdigit(c)) f |= (c == '-'), c = getchar();
while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
s = f ? -s : s;
}
const int _ = 100010;
int tot, head[_], nxt[_ << 1], ver[_ << 1];
inline void Add_edge(int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }
int n, m, rt, val[_];
int dep[_], siz[_], son[_], fa[_];
int top[_], dfn[_], rev[_];
int mn[_ << 2], tag[_ << 2];
inline int lc(int p) { return p << 1; }
inline int rc(int p) { return p << 1 | 1; }
inline void pushup(int p) { mn[p] = min(mn[lc(p)], mn[rc(p)]); }
inline void f(int p, int v) { mn[p] = tag[p] = v; }
inline void pushdown(int p)
{ if (tag[p]) f(lc(p), tag[p]), f(rc(p), tag[p]), tag[p] = 0; }
inline void build(int p = 1, int l = 1, int r = n) {
tag[p] = 0; if (l == r) { mn[p] = val[rev[l]]; return ; }
int mid = (l + r) >> 1;
build(lc(p), l, mid), build(rc(p), mid + 1, r), pushup(p);
}
inline void update(int ql, int qr, int v, int p = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return f(p, v);
int mid = (l + r) >> 1;
pushdown(p);
if (ql <= mid) update(ql, qr, v, lc(p), l, mid);
if (qr > mid) update(ql, qr, v, rc(p), mid + 1, r);
pushup(p);
}
inline int query(int ql, int qr, int p = 1, int l = 1, int r = n) {
if (ql <= l && r <= qr) return mn[p];
int mid = (l + r) >> 1, res = 2147483647;
pushdown(p);
if (ql <= mid) res = min(res, query(ql, qr, lc(p), l, mid));
if (qr > mid) res = min(res, query(ql, qr, rc(p), mid + 1, r));
return res;
}
inline void dfs1(int u, int f) {
siz[u] = 1, fa[u] = f, dep[u] = dep[f] + 1;
for (rg int v, i = head[u]; i; i = nxt[i])
if (!dep[v = ver[i]]) {
dfs1(v, u), siz[u] += siz[v];
if (siz[son[u]] < siz[v]) son[u] = v;
}
}
inline void dfs2(int u, int topf) {
top[rev[dfn[u] = ++dfn[0]] = u] = topf;
if (!son[u]) return; dfs2(son[u], topf);
for (rg int v, i = head[u]; i; i = nxt[i])
if (!top[v = ver[i]]) dfs2(v, v);
}
inline int pson(int x, int y){
int fx = top[x], fy = top[y];
while (fx != fy){
if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
if (fa[fx] == y) return fx; x = fa[fx], fx = top[x];
}
return dep[x] < dep[y] ? son[x] : son[y];
}
inline int LCA(int x, int y) {
int fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
x = fa[fx], fx = top[x];
}
return dep[x] < dep[y] ? x : y;
}
inline void uptRange(int x, int y, int v) {
int fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
update(dfn[fx], dfn[x], v), x = fa[fx], fx = top[x];
}
if (dep[x] > dep[y]) swap(x, y);
return update(dfn[x], dfn[y], v);
}
inline int qSon(int x) {
if (rt == x) return query(1, n);
int lca = LCA(rt, x);
if (lca != x) return query(dfn[x], dfn[x] + siz[x] - 1);
int t = pson(rt, x);
return min(query(1, dfn[t] - 1), query(dfn[t] + siz[t], n));
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
read(n), read(m);
for (rg int u, v, i = 1; i < n; ++i)
read(u), read(v), Add_edge(u, v), Add_edge(v, u);
for (rg int i = 1; i <= n; ++i) read(val[i]);
read(rt), dfs1(rt, 0), dfs2(rt, rt), build();
for (int opt, x, y, v; m--; ) {
read(opt);
if (opt == 1) read(rt);
else if (opt == 2) read(x), read(y), read(v), uptRange(x, y, v);
else if (opt == 3) read(x), printf("%d
", qSon(x));
}
return 0;
}
完结撒花 (qwq)