专栏首页数据结构与算法BZOJ3083: 遥远的国度(树链剖分)

BZOJ3083: 遥远的国度(树链剖分)

题意

$n$个节点的树,每个点有权值,支持三种操作

1、 换根

2、把$x$到$y$路径上节点权值变为$z$

3、询问路径最小值

Sol

啥?你说这是TopTree的裸题?那你写去啊

很显然,如果没有第一个操作就是树剖的裸题

其实有了第一个操作也是树剖的裸题

我们考虑换根之后会对那些节点产生影响

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

第一种情况:x == root

很显然直接查询子树的最小值就行

第二种情况:$lca(x,root) != x$

这种情况也简单,直接查询$x$子树中的最小值即可

第三种情况:$lca(x,root) = x$

这种情况稍微复杂一些

我们需要找到$root$往上走,离$x$最近的点。

很显然,这个点以上的部分,就是我们要查询的区间

那么我们查询这个点的子树对应区间的补集即可

#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));//tag
    if(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
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2017.10.2解题报告

    预计分数:60+0+30=90 实际分数:60+0+0=60 T1:https://www.luogu.org/problem/show?pid=T...

    attack
  • SPOJ2713GSS4 - Can you answer these queries IV(线段树)

    双倍经验:https://www.luogu.org/problemnew/show/P4145

    attack
  • 洛谷P3924 康娜的线段树(期望 前缀和)

    如果你和我一样为了AC不追求效率的话直接#define int __int128就行了。。

    attack
  • ACM札记之一

    输入n(n<=100)个整数,按照绝对值从大到小排序后输出。题目保证对于每一个测试实例,所有的数的绝对值都不相等。

    慕白
  • 2017.10.2解题报告

    预计分数:60+0+30=90 实际分数:60+0+0=60 T1:https://www.luogu.org/problem/show?pid=T...

    attack
  • 洛谷P3924 康娜的线段树(期望 前缀和)

    如果你和我一样为了AC不追求效率的话直接#define int __int128就行了。。

    attack
  • BZOJ3073: [Pa2011]Journeys(线段树优化建图 Dijkstra)

    attack
  • 51nod 1649 齐头并进(Codeforces 601A The Two Routes) (最短路)

    题目链接(Codeforces):http://codeforces.com/problemset/problem/601/A

    Ch_Zaqdt
  • BZOJ4552: [Tjoi2016&Heoi2016]排序(线段树 二分)

    首先二分一个答案,表示假设询问的位置为$x$,把$>= x$的看成$1$,$< x$的看成$0$

    attack
  • P1197 [JSOI2008]星球大战

    题目描述 很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几...

    attack

扫码关注云+社区

领取腾讯云代金券