Luogu3979 遥远的国度

发布于 2020-12-02  195 次阅读


Link

Sol

换根树剖是个假的, 只要讨论新根在的位置就好了

分三种情况

第一种换的新根就是现在的根,那么该咋就咋(我也不知道为什么所有的题解都要讨论这种情况,但是我还是讨论了)

第二种就是换的新根和原来的根的lca就是新根,也就是说,原来的跟就在新根的子树中, 那么要操作的实际位置是新根的下面一个点

第三种就是新根和原来的根在以第一个根为根的树中分属不同的子树中,那么换根的操作实际上啥影响也没有.直接在新根的子树中查就可以了

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 1e5 + 5;
const int inf = 0x7f7f7f7f;

int n, m, num, ind, root;
int head[SIZE], dfn[SIZE], dep[SIZE], fa[SIZE], idx[SIZE], w[SIZE], son[SIZE], siz[SIZE], bel[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];

struct seg {
    int l, r, minn, tag;
} tree[SIZE << 2];

namespace ae86 {
    const int bufl = 1 << 15;
    char buf[bufl], *s = buf, *t = buf;
    inline int fetch() {
        if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
        return *s++;
    }
    inline int read() {
        int a = 0, b = 1, c = fetch();
        while (!isdigit(c))b ^= c == '-', c = fetch();
        while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
        return b ? a : -a;
    }
}
using ae86::read;

inline void addEdge(int u, int v) {
    edge[++ num].to = v, edge[num].nxt = head[u];
    head[u] = num;
}

inline void dfs1(int u, int ff) {
    siz[u] = 1;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == ff) continue;
        fa[v] = u, dep[v] = dep[u] + 1;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

inline void dfs2(int u, int top) {
    dfn[u] = ++ ind, idx[ind] = u, bel[u] = top;
    if (son[u]) dfs2(son[u], top);
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1

inline void pushUp(int p) {
    tree[p].minn = std::min(tree[lson(p)].minn, tree[rson(p)].minn);
}

inline void pushDown(int p) {
    if (tree[p].tag != inf) {
        tree[lson(p)].minn = tree[rson(p)].minn = tree[p].tag;
        tree[lson(p)].tag = tree[rson(p)].tag = tree[p].tag;
        tree[p].tag = inf;
    }
}

inline void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r, tree[p].minn = tree[p].tag = inf;
    if (l == r) {
        tree[p].minn = w[idx[l]], tree[p].tag = inf;
        return;
    }
    int mid = (l + r) >> 1;
    build(lson(p), l, mid); build(rson(p), mid + 1, r);
    pushUp(p);
}

inline void modify(int p, int l, int r, int val) {
    if (l <= tree[p].l && tree[p].r <= r) {
        tree[p].minn = val, tree[p].tag = val;
        return;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if (l <= mid) modify(lson(p), l, r, val);
    if (r > mid) modify(rson(p), l, r, val);
    pushUp(p);
}

inline int queryMin(int p, int l, int r) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].minn;
    }
    pushDown(p);
    int mid = (tree[p].l + tree[p].r) >> 1, ans = inf;
    if (l <= mid) ans = std::min(ans, queryMin(lson(p), l, r));
    if (r > mid) ans = std::min(ans, queryMin(rson(p), l, r));
    return ans;
}

inline int lca(int u, int v) {
    while (bel[u] != bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        u = fa[bel[u]];
    }
    return dfn[u] > dfn[v] ? v : u;
}

inline void modifyPath(int u, int v, int val) {
    while (bel[u] != bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        modify(1, dfn[bel[u]], dfn[u], val);
        u = fa[bel[u]];
    }   
    if (dfn[u] > dfn[v]) std::swap(u, v);
    modify(1, dfn[u], dfn[v], val);
}

inline int queryPath(int u, int v) {
    int ans = inf;
    while (bel[u] != bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        ans = std::min(ans, queryMin(1, dfn[bel[u]], dfn[u]));
        u = fa[bel[u]];
    }
    if (dfn[u] > dfn[v]) std::swap(u, v);
    ans = std::min(ans, queryMin(1, dfn[u], dfn[v]));
    return ans;
}

inline int find(int u, int v) {
    while (bel[u] != bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        if (fa[bel[u]] != v) u = fa[bel[u]];
        else return bel[u];
    }
    // if (dep[u] < dep[v]) std::swap(u, v);
    // return son[v];
    return dfn[u] > dfn[v] ? son[v] : son[u];
}       

inline int ask(int rt) {
    if (rt == root) return queryMin(1, 1, n);
    int ff = lca(root, rt), ans = inf;
    if (rt == ff) {
        int u = find(rt, root);
        if (dfn[u] > 1) ans = std::min(queryMin(1, 1, dfn[u] - 1),ans);
        if (dfn[u] + siz[u] <= n) ans = std::min(queryMin(1, dfn[u] + siz[u], n), ans);
        return ans; 
    }
    else return queryMin(1, dfn[rt], dfn[rt] + siz[rt] - 1); 
}

signed main() {
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    n = read(), m = read();
    for (int i = 1, u, v; i < n; ++ i) {
        u = read(), v = read();
        addEdge(u, v); addEdge(v, u);
    }
    for (int i = 1; i <= n; ++ i) w[i] = read();
    root = read();
    dfs1(root, 0); dfs2(root, root);
    build(1, 1, n);
    int opt, u, v, d;   
    while (m --) {
        opt = read();
        if (opt == 1) root = read();
        else if (opt == 2) {
            u = read(), v = read(), d = read();
            modifyPath(u, v, d);
        }
        else if (opt == 3) {
            u = read();
            printf("%lld\n", ask(u));
        }
    }
    return 0;
}

生存 关心