← Real problems

sdoi17r1p2

unratedStatement on DMOJ

CP Lang

25 lines0.3 spec
// SDOI 2017 "Tree Painting": every node starts with its own colour. Paint a
// root path with a fresh colour; count colours on a path; maximize the colour
// count to the root over a subtree. Colour classes are preferred paths, so
// painting is an access, and each path switch shifts one subtree's counts.
enum Op = Paint(x: V) | Path(x: V, y: V) | Deepest(x: V)

let (n, q) = read<(1..=1e5, 1..=1e5)>()
domain V = 1..=n
let t = Rooted(Graph.undirected(read<[n - 1](u: V, v: V)>()), root: V.first!)
let lca = LcaTable(t)
var colours = SegTree(max, [t.Pre] p => t.depth(t.at(p)) + 1, act: add)
var paths = PreferredPaths(t)

for op in read<[q]Op>():
    match op:
        Paint(x) =>
            for (lost, gained) in paths.access(x):
                if lost is Some(top):
                    colours.apply(t.sub(top), 1)
                colours.apply(t.sub(gained), -1)
        Path(x, y) =>
            let at = (v: V) => colours.fold(t.pos(v)..=t.pos(v))
            print(at(x) + at(y) - 2 * at(lca.lca(x, y)) + 1)
        Deepest(x) =>
            print(colours.fold(t.sub(x)))

Accepted C++

417 lines · 2.21 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct Node {
    int l, r, v;

    Node operator+(const Node& n) const {
        return {l, n.r, v + n.v + (r != n.l)};
    }

    Node reversed() const {
        return {r, l, v};
    }

    static Node c_from(int x) {
        return {x, x, 0};
    }

    static Node merge(const optional<Node>& a, const Node& b) {
        if (!a) {
            return b;
        }
        return a.value() + b;
    }

    static Node merge(const Node& a, const optional<Node>& b) {
        if (!b) {
            return a;
        }
        return a + b.value();
    }
};

struct ST1 {
    int n;
    vector<Node> v, arr;
    vector<int> lazy;

    ST1() {}
    ST1(const vector<Node>& arr)
        : n(sz(arr)), v(4 * n), arr(arr), lazy(4 * n, -1) {
        build(1, 0, n - 1);
    }

    void build(int o, int l, int r) {
        if (l == r) {
            v[o] = arr[l];
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = v[lc] + v[rc];
    }

    void maintain(int o, int l, int r) {
        if (lazy[o] != -1) {
            v[o] = Node::c_from(lazy[o]);
            return;
        }
        if (l == r) {
            v[o] = arr[l];
        } else {
            v[o] = v[o * 2] + v[o * 2 + 1];
        }
    }

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            lazy[o] = x;
            maintain(o, l, r);
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (lazy[o] != -1) {
            lazy[lc] = lazy[rc] = lazy[o];
            lazy[o] = -1;
        }
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        } else {
            maintain(lc, l, mid);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        } else {
            maintain(rc, mid + 1, r);
        }
        maintain(o, l, r);
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    Node query(int o, int l, int r, int ql, int qr) const {
        if (lazy[o] != -1) {
            return Node::c_from(lazy[o]);
        }
        if (ql <= l && r <= qr) {
            return v[o];
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            if (mid < qr) {
                return query(lc, l, mid, ql, qr) +
                       query(rc, mid + 1, r, ql, qr);
            }
            return query(lc, l, mid, ql, qr);
        }
        return query(rc, mid + 1, r, ql, qr);
    }

    Node query(int l, int r) const {
        return query(1, 0, n - 1, l, r);
    }

    int query_get(int ind) const {
        return query(ind, ind).l;
    }
};

struct ST2 {
    int n;
    vector<int> v, arr, lazy;

    ST2() {}
    ST2(const vector<int>& arr)
        : n(sz(arr)), v(4 * n), arr(arr), lazy(4 * n) {
        build(1, 0, n - 1);
    }

    void build(int o, int l, int r) {
        if (l == r) {
            v[o] = arr[l];
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = max(v[lc], v[rc]);
    }

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            v[o] += x;
            lazy[o] += x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        }
        v[o] = lazy[o] + max(v[lc], v[rc]);
    }

    void update(int l, int r, int x) {
        update(1, 0, n - 1, l, r, x);
    }

    int query(int o, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) {
            return v[o];
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1, ans = 0;
        if (ql <= mid) {
            ans = max(ans, query(lc, l, mid, ql, qr));
        }
        if (mid < qr) {
            ans = max(ans, query(rc, mid + 1, r, ql, qr));
        }
        return ans + lazy[o];
    }

    int query(int l, int r) const {
        return query(1, 0, n - 1, l, r);
    }
};

constexpr int maxn = 1e5 + 5, logn = 20;

int cc, tin[maxn], tout[maxn], par[maxn], siz[maxn], up[maxn], lift[logn][maxn],
    depth[maxn], ch[maxn];
vector<int> graph[maxn], ord;
set<int> sbad;
ST1 st1;
ST2 st2;

void dfs1(int u, int p, int d) {
    par[u] = lift[0][u] = p;
    siz[u] = 1;
    depth[u] = d;
    for (auto& v : graph[u]) {
        graph[v].erase(find(begin(graph[v]), end(graph[v]), u));
        dfs1(v, u, d + 1);
        siz[u] += siz[v];
        if (siz[v] > siz[graph[u][0]]) {
            swap(v, graph[u][0]);
        }
    }
}

void dfs2(int u) {
    tin[u] = cc++;
    ord.push_back(u);
    if (sz(graph[u])) {
        up[graph[u][0]] = up[u];
    }
    for (auto& v : graph[u]) {
        dfs2(v);
    }
    tout[u] = cc;
}

bool anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    if (anc(u, v)) {
        return u;
    }
    for (int i = logn - 1; i >= 0; i--) {
        int cu = lift[i][u];
        if (cu != -1 && !anc(cu, v)) {
            u = cu;
        }
    }
    return par[u];
}

Node query_anc(int u, int v) {
    assert(anc(u, v));
    optional<Node> ans;
    while (true) {
        int lv = max(tin[u], tin[up[v]]);
        dbg(lv, tin[v]);
        ans = Node::merge(st1.query(lv, tin[v]), ans);
        if (lv == tin[u]) {
            break;
        }
        v = par[up[v]];
    }
    return ans.value();
}

void subtree_add(int u, int x) {
    dbg(u, x);
    st2.update(tin[u], tout[u] - 1, x);
}

int get(int u) {
    return st1.query_get(tin[u]);
}

void update_st2(int u) {
    int pu = -1;
    while (u >= 0) {
        auto check_ch = [&](int v) -> void {
            int cv = ch[v];
            if (cv == -1 || get(v) != get(cv)) {
                return;
            }
            dbg(v, cv);
            subtree_add(cv, +1);
        };
        auto check_chain = [&](int v, int cv) -> void {
            if (get(v) != get(cv)) {
                subtree_add(cv, -1);
            }
        };
        for (auto it = sbad.lower_bound(tin[up[u]]);
             it != sbad.end() && *it < tin[u]; it = sbad.erase(it)) {
            int v = ord[*it], cv = graph[v][0];
            check_chain(v, cv);
            check_ch(v);
        }
        if (pu != -1) {
            check_chain(u, pu);
        }
        if (ch[u] != pu) {
            check_ch(u);
        }
        if (sz(graph[u]) && get(u) == get(graph[u][0])) {
            subtree_add(graph[u][0], +1);
        }
        if (pu != -1) {
            ch[u] = pu;
        } else {
            ch[u] = -1;
        }
        pu = up[u];
        sbad.insert(tin[u]);
        u = par[up[u]];
    }
}

void update_st1(int u, int ind) {
    while (u >= 0) {
        int lu = tin[up[u]];
        st1.update(lu, tin[u], ind);
        u = par[up[u]];
    }
}

void update(int u, int ind) {
    dbg(u, ind);
    update_st2(u);
    update_st1(u, ind);
    dbg(st1.query_get(0), st1.query_get(2));
}

void solve() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs1(0, -1, 0);
    iota(up, up + n, 0);
    dfs2(0);
    for (int i = 1; i < logn; i++) {
        for (int j = 0; j < n; j++) {
            if (lift[i - 1][j] == -1) {
                lift[i][j] = -1;
            } else {
                lift[i][j] = lift[i - 1][lift[i - 1][j]];
            }
        }
    }
    int cind = 0;
    {
        vector<Node> stv1;
        for (int i = 0; i < n; i++) {
            stv1.push_back(Node::c_from(cind++));
        }
        st1 = stv1;
    }
    {
        vector<int> stv2(n);
        for (int i = 0; i < n; i++) {
            stv2[tin[i]] = depth[i] + 1;
        }
        st2 = stv2;
    }
    fill(ch, ch + n, -1);
    for (int i = 0; i < n; i++) {
        sbad.insert(i);
    }
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int u;
            cin >> u;
            u--;
            update(u, cind++);
        } else if (t == 2) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            int l = lca(u, v);
            auto nu = query_anc(l, u).reversed(), nv = query_anc(l, v);
            cout << (nu + nv).v + 1 << endl;
        } else {
            assert(t == 3);
            int u;
            cin >> u;
            u--;
            cout << st2.query(tin[u], tout[u] - 1) << endl;
        }
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}