Luogu 3979 遥远的国度

树剖已经是人尽皆知的sb题了吗……

很早以前就想填掉这坑了……

考虑到树链唯一，进行操作并不会对换根产生影响，那么我们的换根操作只要记下root在哪里就好了

询问的时候分类讨论：

1：root == x 直接返回全树最大值就好了

2：lca（root， x）！= x，那就和x没什么关系了，只要返回原子树最大值就好了

3：lca（root， x） == x，说明x在root的上方，那么找到x的儿子中root的祖先y，除了y的子树就都是x的子树了

跳树链和找lca可以用倍增实现

总复杂度 O(nlog²n)

Code（写的很长……）：

#include <cstdio>

using namespace std;

const int N = 1e5 + ;

const int Lg = ;

const int inf =  << ;

int n, qn, a[N], tot = , head[N], root;

int dfsc = , id[N], siz[N], top[N];

int w[N], dep[N], fa[N][Lg], son[N];

struct Edge {

    int to, nxt;

} e[N << ];

inline void add(int from, int to) {

    e[++tot].to = to;

    e[tot].nxt = head[from];

    head[from] = tot;

}

inline void read(int &X) {

    X = ;

    char ch = ;

    int op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline int min(int x, int y) {

    return x > y ? y : x;

}

inline void chkMin(int &x, int y) {

    if(y < x) x = y;

}

inline void swap(int &x, int &y) {

    int t = x;

    x = y;

    y = t;

}

void dfs1(int x, int fat, int depth) {

    siz[x] = , fa[x][] = fat, dep[x] = depth;

    for(int i = ; i <= ; i++)

        fa[x][i] = fa[fa[x][i - ]][i - ];

    int maxson = -;

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(y == fat) continue;

        dfs1(y, x, depth + );

        siz[x] += siz[y];

        if(siz[y] > maxson)

            maxson = siz[y], son[x] = y;

    }

}

void dfs2(int x, int topf) {

    w[id[x] = ++dfsc] = a[x], top[x] = topf;

    if(!son[x]) return;

    dfs2(son[x], topf);

    for(int i = head[x]; i; i = e[i].nxt) {

        int y = e[i].to;

        if(y == fa[x][] || y == son[x]) continue;

        dfs2(y, y);

    }

}

inline int getLca(int x, int y) {

    if(dep[x] < dep[y]) swap(x, y);

    for(int i = ; i >= ; i--)

        if(dep[fa[x][i]] >= dep[y])

            x = fa[x][i];

    if(x == y) return x;

    for(int i = ; i >= ; i--)

        if(fa[x][i] != fa[y][i])

            x = fa[x][i], y = fa[y][i];

    return fa[x][];

}

namespace SegT {

    int s[N << ], tag[N << ];

    #define lc p << 1

    #define rc p << 1 | 1

    #define mid ((l + r) >> 1)

    inline void up(int p) {

        if(p) s[p] = min(s[lc], s[rc]);

    }

    inline void down(int p) {

        if(tag[p] == inf) return;

        s[lc] = tag[lc] = s[rc] = tag[rc] = tag[p];

        tag[p] = inf;

    }

    void build(int p, int l, int r) {

        tag[p] = inf;

        if(l == r) {

            s[p] = w[l];

            return;

        }

        build(lc, l, mid);

        build(rc, mid + , r);

        up(p);

    }

    void modify(int p, int l, int r, int x, int y, int v) {

        if(x <= l && y >= r) {

            s[p] = tag[p] = v;

            return;

        }

        down(p);

        if(x <= mid) modify(lc, l, mid, x, y, v);

        if(y > mid) modify(rc, mid + , r, x, y, v);

        up(p);

    }

    int query(int p, int l, int r, int x, int y) {

        if(x <= l && y >= r) return s[p];

        down(p);

        int res = inf;

        if(x <= mid) chkMin(res, query(lc, l, mid, x, y));

        if(y > mid) chkMin(res, query(rc, mid + , r, x, y));

        return res;

    }

} using namespace SegT;

inline void mtree(int x, int y, int v) {

    for(; top[x] != top[y]; ) {

        if(dep[top[x]] < dep[top[y]]) swap(x, y);

        modify(, , n, id[top[x]], id[x], v);

        x = fa[top[x]][];

    }

    if(dep[x] > dep[y]) swap(x, y);

    modify(, , n, id[x], id[y], v);

}

inline int ask(int x) {

    if(root == x) return s[];

    int y = getLca(x, root);

    if(y == x) {

        int z = root;

        for(int i = ; i >= ; i--)

            if(dep[fa[z][i]] > dep[y])

                z = fa[z][i];

        return min(query(, , n, , id[z] - ), query(, , n, id[z] + siz[z], n));

    } else return query(, , n, id[x], id[x] + siz[x] - );

}

int main() {

    read(n), read(qn);

    for(int x, y, i = ; i < n; i++) {

        read(x), read(y);

        add(x, y), add(y, x);

    }

    dfs1(, , );

    for(int i = ; i <= n; i++) read(a[i]);

    dfs2(, );

    build(, , n);

    read(root);

    for(int op; qn--; ) {

        read(op);

        if(op == ) read(root);

        if(op == ) {

            int x, y, v;

            read(x), read(y), read(v);

            mtree(x, y, v);

        }

        if(op == ) {

            int x;

            read(x);

            printf("%d\n", ask(x));

        }

    }

    return ;

}

巴特西

Luogu 3979 遥远的国度

最新文章

热门文章