bzoj 4551 [Tjoi2016&Heoi2016]树 树剖+线段树
发布日期:2021-10-25 03:44:51 浏览次数:0 分类:技术文章

题面

解法

并查集的方法感觉十分精妙,见
树剖+线段树也比较简单吧

维护区间的答案,合并的时候根据深度判断大小

时间复杂度:\(O(q\ log^2\ n)\)

代码

#include <bits/stdc++.h>#define N 100010using namespace std;template <typename node> void read(node &x) {    x = 0; int f = 1; char c = getchar();    while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}    while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;}int n, q, cnt, Time;int dfn[N], siz[N], top[N], d[N], f[N], son[N];struct Edge {    int next, num;} e[N * 3];struct SegmentTree {    struct Node {        int l, r, mx;    } t[N * 4];    void build(int k, int l, int r) {        t[k] = (Node) {l, r, n + 1};        if (l == r) return;        int mid = (l + r) >> 1;        build(k << 1, l, mid);        build(k << 1 | 1, mid + 1, r);    }    void update(int k) {        int x = t[k << 1].mx, y = t[k << 1 | 1].mx;        t[k].mx = (d[x] > d[y]) ? x : y;    }    void modify(int k, int x, int num) {        int l = t[k].l, r = t[k].r;        if (l == r) {t[k].mx = num; return;}        int mid = (l + r) >> 1;        if (x <= mid) modify(k << 1, x, num);            else modify(k << 1 | 1, x, num);        update(k);    }    int query(int k, int L, int R) {        int l = t[k].l, r = t[k].r;        if (L <= l && r <= R) return t[k].mx;        int mid = (l + r) >> 1;        if (R <= mid) return query(k << 1, L, R);        if (L > mid) return query(k << 1 | 1, L, R);        int x = query(k << 1, L, mid), y = query(k << 1 | 1, mid + 1, R);        return (d[x] > d[y]) ? x : y;    }} T;void add(int x, int y) {    e[++cnt] = (Edge) {e[x].next, y};    e[x].next = cnt;}void dfs1(int x, int fa) {    d[x] = d[fa] + 1, siz[x] = 1, f[x] = fa;    for (int p = e[x].next; p; p = e[p].next) {        int k = e[p].num;        if (k == fa) continue;         dfs1(k, x); siz[x] += siz[k];        if (siz[son[x]] < siz[k]) son[x] = k;    }}void dfs2(int x, int tp) {    top[x] = tp, dfn[x] = ++Time;    if (!son[x]) return; dfs2(son[x], tp);    for (int p = e[x].next; p; p = e[p].next) {        int k = e[p].num;        if (k == f[x] || k == son[x]) continue;        dfs2(k, k);    }}int Query(int x) {    int fx = top[x];    while (fx != 1) {        int tmp = T.query(1, dfn[fx], dfn[x]);        if (tmp != n + 1) return tmp;        x = f[fx], fx = top[x];    }    return T.query(1, dfn[1], dfn[x]);}int main() {    read(n), read(q); cnt = n;    for (int i = 1; i < n; i++) {        int x, y; read(x), read(y);        add(x, y), add(y, x);    }    dfs1(1, 0); dfs2(1, 0); d[n + 1] = 0;    T.build(1, 1, n); T.modify(1, dfn[1], 1);    while (q--) {        char c = getchar(); int x;        while (!isalpha(c)) c = getchar();        read(x);        if (c == 'C') T.modify(1, dfn[x], x);            else cout << Query(x) << "\n";    }    return 0;}

转载于:https://www.cnblogs.com/copperoxide/p/9478715.html

上一篇:SQL HAVING 子句
下一篇:关于this的用法,网上看到一个非常好的判断方法。