题目链接：https://www.luogu.org/problemnew/show/P3979
除了换根操作都是裸的树剖
所以换根时考虑：
1.我查询的根等于换的根：无影响
2.我查询的根是换的根的子树：无影响
3.我查询的根是换的根的祖先：查询 除换的根及其往上直到为要查询的根的第一层儿子的祖先(设为S)的子树 以外的所有节点 (此时满足seg[S] <= seg[root] <= seg[S]+size[S]-1)
求LCA 查询1到seg[S]-1 和 seg[S]+size[S]到n 正好避开子树seg[S] 到 seg[S]+size[S]-1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define lson left, mid, rt<<1
#define rson mid + 1, right, rt<<1|1
using namespace std;
const ll maxn = 200000 + 10;
ll tree[maxn<<2], lazy[maxn<<2];
ll seg[maxn], fa[maxn], size[maxn], rev[maxn], son[maxn], deep[maxn], top[maxn], num;
ll node[maxn], res, n, m, root, r;
struct edge{
ll from, to, next;
}e[maxn<<2];
ll head[maxn], cnt;
void add(ll u, ll v)
{
e[++cnt].from = u;
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt;
}
//--------------------------segment_tree
void PushUP(ll rt)
{
tree[rt] = min(tree[rt<<1], tree[rt<<1|1]);
}
void build(ll left, ll right, ll rt)
{
if(left == right)
{
tree[rt] = rev[left];
return;
}
ll mid = (left + right)>>1;
build(lson);
build(rson);
PushUP(rt);
}
void PushDOWN(ll rt)
{
lazy[rt<<1] = lazy[rt];
lazy[rt<<1|1] = lazy[rt];
tree[rt<<1] = lazy[rt];
tree[rt<<1|1] = lazy[rt];
lazy[rt] = 0;
}
void update(ll l, ll r, ll add, ll left, ll right, ll rt)
{
if(l <= left && r >= right)
{
tree[rt] = add;
lazy[rt] = add;
return;
}
ll mid = (left + right)>>1;
if(lazy[rt]) PushDOWN(rt);
if(l <= mid) update(l, r, add, lson);
if(r > mid) update(l, r, add, rson);
PushUP(rt);
}
ll query(ll l, ll r, ll left, ll right, ll rt)
{
ll res = 0x7fffffff;
if(l <= left && r >= right)
{
return tree[rt];
}
ll mid = (left + right)>>1;
if(lazy[rt]) PushDOWN(rt);
if(l <= mid) res = min(res, query(l, r, lson));
if(r > mid) res = min(res, query(l, r, rson));
return res;
}
//------------------------
void dfs1(ll u, ll f, ll d)
{
ll maxson = -1;
size[u] = 1;
deep[u] = d;
fa[u] = f;
for(ll i = head[u]; i != -1; i = e[i].next)
{
ll v = e[i].to;
if(f != v)
{
dfs1(v, u, d+1);
size[u] += size[v];
if(size[v] > maxson) son[u] = v, maxson = size[v];
}
}
}
void dfs2(ll u, ll t)
{
seg[u] = ++num;
rev[num] = node[u];
top[u] = t;
if(!son[u]) return;
dfs2(son[u], t);
for(ll i = head[u]; i != -1; i = e[i].next)
{
ll v = e[i].to;
if(v == son[u] || v == fa[u]) continue;
dfs2(v,v);
}
}
/*ll qRange(ll x, ll y)
{
ll ans = 0;
while(top[x] != top[y])
{
if(deep[top[x]] < deep[top[y]]) swap(x, y);
res = 0;
res = query(seg[top[x]], seg[x], 1, n, 1);
ans = (ans + res);
x = fa[top[x]];
}
if(deep[x] > deep[y]) swap(x, y);
res = 0;
res = query(seg[x], seg[y], 1, n, 1);
ans = (ans + res);
return ans;
}*/
void updRange(ll x, ll y, ll k)
{
while(top[x] != top[y])
{
if(deep[top[x]] < deep[top[y]]) swap(x, y);
update(seg[top[x]], seg[x], k, 1, n, 1);
x = fa[top[x]];
}
if(deep[x] > deep[y]) swap(x, y);
update(seg[x], seg[y], k, 1, n, 1);
}
ll LCA(int x, int y)
{
while(top[x] != top[y])
{
if(deep[top[x]] < deep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return deep[x] < deep[y] ? x : y;
}
ll qSon(ll x)
{
if(x == r)
return query(1, n, 1, n, 1);
int p = LCA(r, x);
if(p != x)
return query(seg[x], seg[x]+size[x]-1, 1, n, 1);
int S;
for(int i = head[x]; i != -1; i = e[i].next)
{
int v = e[i].to;
if(seg[v] <= seg[r] && seg[r] <= seg[v] + size[v] -1 && v != fa[x])
{
S = v; break;
}
}
return min(query(1, seg[S]-1, 1, n, 1), query(seg[S]+size[S], n, 1, n, 1));
}
int main()
{
memset(head, -1, sizeof(head));
scanf("%lld%lld",&n,&m);
for(ll i = 1; i < n; i++)
{
ll u, v;
scanf("%lld%lld",&u,&v);
add(u, v), add(v, u);
}
for(ll i = 1; i <= n; i++)
scanf("%lld",&node[i]);
scanf("%lld",&root);
dfs1(root, 0, 1);
dfs2(root, root);
build(1,n,1);
r = root;
for(ll i = 1; i <= m; i++)
{
ll opt, x, y, z;
scanf("%lld",&opt);
if(opt == 1)
{
scanf("%lld",&x);
r = x;
}
if(opt == 2)
{
scanf("%lld%lld%lld",&x,&y,&z);
updRange(x, y, z);
}
if(opt == 3)
{
scanf("%lld",&x);
printf("%lld
",qSon(x));
}
}
return 0;
}