P3979 遥远的国度
题意
一棵树,\(n\le 10^5\),三个操作,\(m\le 10^5\),点带权。
- 换根
- 路径推平
- 子树查最小值
思路
如果没有换根,操作 2, 3 是裸的树剖,考虑换根后的询问如何处理。
显然不能再做一遍树剖,只能假装我们换根了,询问可以分成四种情况,令原根为 \(root\),新根为 \(id\),查询点为 \(x\):
- \(x = id\),全局最小值;
- \(x\) 在 \(id\) 的子树内,原子树最小值
- \(x\) 在 \(root\) 到 \(id\) 的路径上,即 \(id\) 在 \(x\) 的原子树内,则询问等价于除了以 \(id\) 所在的 \(x\) 的子树中所有点的查询。
- \(x\) 和 \(id\) 不在同一颗 \(root\) 的子树内, 原子树最小值。
最棘手的是情况 3,如果 \(\min\) 的贡献可以消除,只需要用全局贡献减去子树贡献,然而 \(\min\) 操作的属性并不支持贡献的消除,所以只能反向考虑问题,由于子树内的点的编号是连续的,所以可以考虑合并左半部分的贡献与右半部分的贡献。
如果 \(LCA(x, id) = x\),则 \(id\) 在 \(x\) 的子树内
// Problem: P3979 遥远的国度
// Author: Moyou
// Copyright (c) 2023 Moyou All rights reserved.
// Date: 2023-07-29 13:47:25
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#define int long long
#define inf (int)2e18
using namespace std;
const int N = 1e5 + 10;
int n, m, temp[N];
vector<int> g[N];
int sz[N], hson[N], dfn[N], id[N], top[N], fa[N], w[N], tmst, dep[N];
void dfs1(int u, int fat)
{
fa[u] = fat, sz[u] = 1, dep[u] = dep[fat] + 1;
for(auto v : g[u])
{
if(v == fa[u]) continue;
dfs1(v, u);
sz[u] += sz[v];
if(sz[v] > sz[hson[u]])
hson[u] = v;
}
}
void dfs2(int u, int anc)
{
dfn[++ tmst] = u, id[u] = tmst, w[tmst] = temp[u], top[u] = anc;
if(!hson[u]) return ;
dfs2(hson[u], anc);
for(auto v : g[u])
{
if(v == fa[u] || v == hson[u]) continue;
dfs2(v, v);
}
}
// The code below implemented a Segment Tree
struct qwq
{
int l, r, dat, tag;
} tr[N << 2];
void up(int u)
{
tr[u].dat = min(tr[u << 1].dat, tr[u << 1 | 1].dat);
}
void down(int u)
{
if(tr[u].tag == 0) return ;
tr[u << 1].dat = tr[u << 1 | 1].dat = tr[u].tag;
tr[u << 1].tag = tr[u << 1 | 1].tag = tr[u].tag;
tr[u].tag = 0;
}
void build(int u, int l, int r)
{
tr[u] = {l, r, inf, 0};
if(l == r) tr[u].dat = w[l], tr[u].tag = w[l]; // TODO
else build(u << 1, l, l + r >> 1), build(u << 1 | 1, (l + r >> 1) + 1, r), up(u);
}
void update(int u, int ql, int qr, int v)
{
int l = tr[u].l, r = tr[u].r, mid = l + r >> 1;
if (ql <= l && qr >= r)
{
tr[u].dat = v, tr[u].tag = v;
return;
}
down(u);
if (ql <= mid) update(u << 1, ql, qr, v);
if (qr > mid) update(u << 1 | 1, ql, qr, v);
up(u);
}
int query(int u, int ql, int qr)
{
int l = tr[u].l, r = tr[u].r, mid = l + r >> 1;
if (ql <= l && qr >= r)
return tr[u].dat;
down(u);
int tmp = inf;
if (ql <= mid) tmp = query(u << 1, ql, qr);
if (qr > mid) tmp = min(tmp, query(u << 1 | 1, ql, qr));
up(u);
return tmp;
}
int LCA(int a, int b)
{
while(top[a] != top[b])
{
if(dep[top[a]] < dep[top[b]]) b = fa[top[b]];
else a = fa[top[a]];
}
return (dep[a] < dep[b] ? a : b);
}
void HLDupdate(int a, int b, int v)
{
while(top[a] != top[b])
{
if(dep[top[a]] < dep[top[b]]) swap(a, b);
update(1, id[top[a]], id[a], v);
a = fa[top[a]];
}
if(dep[top[a]] > dep[top[b]]) swap(a, b);
update(1, id[a], id[b], v);
}
int jump(int x, int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
if(fa[top[x]] == y) return top[x];
x = fa[top[x]];
}
return (dep[x] < dep[y] ? hson[x] : hson[y]);
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
n = read(), m = read();
for(int i = 1, a, b; i < n; i ++)
a = read(), b = read(), g[a].push_back(b), g[b].push_back(a);
for(int i = 1; i <= n; i ++)
temp[i] = read();
dfs1(1, 1), dfs2(1, 1);
build(1, 1, n);
int root = read();
while(m --)
{
int op, a, b, c;
op = read();
if(op == 1)
root = read();
else if(op == 2)
{
a = read(), b = read(), c = read();
HLDupdate(a, b, c);
}
else
{
int x = read();
if(root == x)
cout << query(1, 1, n) << '\n';
else
{
int y = jump(root, x);
if(LCA(x, root) == x)
cout << min(query(1, 1, id[y] - 1), (id[y] + sz[y] <= n ? query(1, id[y] + sz[y], n) : inf)) << '\n';
else
cout << query(1, id[x], id[x] + sz[x] - 1) << '\n';
}
}
}
return 0;
}
标签:hson,int,题解,top,tr,dep,国度,P3979,id
From: https://www.cnblogs.com/MoyouSayuki/p/17590205.html