題意

$n$個(gè)節(jié)點(diǎn)的樹，每個(gè)點(diǎn)有權(quán)值，支持三種操作

1、 換根

2、把$x$到$y$路徑上節(jié)點(diǎn)權(quán)值變?yōu)?z$

3、詢問路徑最小值

Sol

啥？你說這是TopTree的裸題？那你寫去啊

很顯然，如果沒有第一個(gè)操作就是樹剖的裸題

其實(shí)有了第一個(gè)操作也是樹剖的裸題

我們考慮換根之后會(huì)對那些節(jié)點(diǎn)產(chǎn)生影響

以下圖片來自(https://blog.csdn.net/lcomyn/article/details/45718295)

第一種情況：x == root

很顯然直接查詢子樹的最小值就行

?

第二種情況：$lca(x,root) != x$

這種情況也簡單，直接查詢$x$子樹中的最小值即可

第三種情況：$lca(x,root) = x$

這種情況稍微復(fù)雜一些

我們需要找到$root$往上走，離$x$最近的點(diǎn)。

很顯然，這個(gè)點(diǎn)以上的部分，就是我們要查詢的區(qū)間

那么我們查詢這個(gè)點(diǎn)的子樹對應(yīng)區(qū)間的補(bǔ)集即可

#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 1e5 + 10, B = 20, INF = 2147483646; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, M, root = 1; int a[MAXN], b[MAXN]; vector<int> v[MAXN]; int fa[MAXN], top[MAXN], jump[MAXN][21], deep[MAXN], siz[MAXN], l[MAXN], r[MAXN], tot = 0, cnt, son[MAXN], ID[MAXN]; void dfs1(int x, int _fa) {fa[x] = _fa; siz[x] = 1; l[x] = ++cnt; jump[x][0] = fa[x];for(int i = 0; i < v[x].size(); i++) {int to = v[x][i];if(deep[to]) continue;deep[to] = deep[x] + 1;dfs1(to, x);siz[x] += siz[to];if(siz[to] > siz[son[x]]) son[x] = to;}r[x] = cnt; } void dfs2(int x, int topf) {top[x] = topf; ID[x] = ++tot; a[tot] = b[x];l[x] = tot;if(!son[x]) {r[x] = tot; return ;}dfs2(son[x], topf);for(int i = 0; i < v[x].size(); i++) {int to = v[x][i];if(top[to]) continue;dfs2(to, to);}r[x] = tot; } void Pre() {for(int i = 1; i <= B; i++) for(int j = 1; j <= N; j++)jump[j][i] = jump[jump[j][i - 1]][i - 1]; } #define ls k << 1 #define rs k << 1 | 1 struct Node {int l, r, mi, si, tag; }T[MAXN * 4]; void update(int k) {T[k].mi = min(T[ls].mi, T[rs].mi);} void ps(int k, int val) {T[k].mi = val; T[k].tag = val; return ;} void pushdown(int k) {if(!T[k].tag) return;ps(ls, T[k].tag); ps(rs, T[k].tag);T[k].tag = 0; } void Build(int k, int ll, int rr) {T[k].l = ll; T[k].r = rr; T[k].si = r - l + 1;if(ll == rr) {T[k].mi = a[ll]; return ;}int mid = ll + rr >> 1;Build(ls, ll, mid); Build(rs, mid + 1, rr);update(k); } void IntervalMem(int k, int ll, int rr, int val) {if(ll <= T[k].l && T[k].r <= rr) {T[k].mi = T[k].tag = val;return;}pushdown(k);int mid = T[k].l + T[k].r >> 1;if(ll <= mid) IntervalMem(ls, ll, rr, val);if(rr > mid) IntervalMem(rs, ll, rr, val);update(k); } void TreeChange(int x, int y, int val) {while(top[x] != top[y]) {if(deep[top[x]] < deep[top[y]]) swap(x, y);IntervalMem(1, ID[top[x]], ID[x], val);x = fa[top[x]];}if(deep[x] < deep[y]) swap(x, y);IntervalMem(1, ID[y], ID[x], val); } int IntervalMin(int k, int ll, int rr) {int ans = INF;if(ll <= T[k].l && T[k].r <= rr) return T[k].mi; pushdown(k);int mid = (T[k].l + T[k].r) >> 1;if(ll <= mid) ans = min(ans, IntervalMin(ls, ll, rr));if(rr > mid) ans = min(ans, IntervalMin(rs, ll, rr));return ans; } int LCA(int x, int y) {while(top[x] != top[y]) {if(deep[top[x]] < deep[top[y]]) swap(x, y); x = fa[top[x]];}if(deep[x] < deep[y]) swap(x, y);return y; } int Find(int rt, int x) {for(int i = B; i >= 0; i--) while(deep[jump[rt][i]] > deep[x])rt = jump[rt][i]; return rt; } int Query(int x) {if(x == root) return T[1].mi;int lca = LCA(x, root);if(lca != x) return IntervalMin(1, l[x], r[x]);int v = Find(root, x), ans = INF;if(l[v] > 1) ans = min(ans, IntervalMin(1, 1, l[v] - 1));//tagif(r[v] < N) ans = min(ans, IntervalMin(1, r[v] + 1, tot));return ans; } int main() {N = read(); M = read();for(int i = 1; i <= N - 1; i++) {int x = read(), y = read();v[x].push_back(y); v[y].push_back(x);}for(int i = 1; i <= N; i++) b[i] = read();root = read(); deep[1] = 1; dfs1(1, 0); dfs2(1, 1);Pre(); Build(1, 1, tot); while(M--) {int opt = read();if(opt == 1) root = read();else if(opt == 2){int x1 = read(), x2 = read(), v = read();TreeChange(x1, x2, v);} else {int x = read();printf("%d\n", Query(x));}}return 0; } /* 3 7 1 2 1 3 1 2 3 1 3 1 2 1 1 6 3 1 2 2 2 5 3 1 2 3 3 4 3 1 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/zwfymqz/p/9364916.html

與50位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的BZOJ3083: 遥远的国度(树链剖分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。