Submission #49508574

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  20.01.2024 18:36
**/
#include <bits/stdc++.h>

using i64 = long long;

template <typename T> struct BIT { // 0-based
    int n;
    std::vector<T> bit;

    BIT(int _n) : n(_n), bit(n + 1) {}

    BIT(const std::vector<T> &a) : n((int)a.size()), bit(n + 1) {
        for (int i = 1; i <= n; i++) {
            bit[i] += a[i - 1];
            if (i + (i & -i) <= n)
                bit[i + (i & -i)] += bit[i];
        }
    }

    T query(int i) {
        T ret{};
        for (i++; i > 0; i -= i & -i)
            ret += bit[i];
        return ret;
    }

    // [l, r]
    T query(int l, int r) { return l > r ? T{} : query(r) - query(l - 1); }

    void update(int i, T val) {
        for (i++; i <= n; i += i & -i)
            bit[i] += val;
    }
};

template <typename Info, typename Tag = int>
class Segtree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;

    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p] += v;
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = {};
    }
    Info query(int p, int l, int r, int ql, int qr) {
        if (l >= qr or r <= ql)
            return {};
        if (ql <= l and r <= qr)
            return info[p];
        push(p);
        int m = (l + r) / 2;
        return query(2 * p, l, m, ql, qr) + query(2 * p + 1, m, r, ql, qr);
    }
    void update(int p, int l, int r, int ul, int ur, const Tag &v) {
        if (l >= ur or r <= ul)
            return;
        if (ul <= l and r <= ur) {
            apply(p, v);
            return;
        }
        push(p);
        int m = (l + r) / 2;
        update(2 * p, l, m, ul, ur, v);
        update(2 * p + 1, m, r, ul, ur, v);
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int i, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        push(p);
        int m = (l + r) / 2;
        i < m ? modify(2 * p, l, m, i, v) : modify(2 * p + 1, m, r, i, v);
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    template <typename F>
    int find_first(int p, int l, int r, int fl, int fr, F pred) {
        if (fr <= l or r <= fl or !pred(info[p]))
            return -1;
        if (r - l == 1)
            return l;
        push(p);
        int m = (l + r) / 2;
        int res = find_first(2 * p, l, m, fl, fr, pred);
        if (res == -1)
            res = find_first(2 * p + 1, m, r, fl, fr, pred);
        return res;
    }

public:
    Segtree() : n(0) {}
    Segtree(int _n, Info _v = {}) : Segtree(std::vector(_n, _v)) {}

    template <std::convertible_to<Info> U>
    Segtree(const std::vector<U> &a) : n(a.size()) {
        assert(n > 0);
        int cap = ((1 + !!(n & (n - 1))) << std::__lg(2 * n)) + 1;
        info.resize(cap);
        tag.resize(cap);
        auto build = [&](auto &&self, int p, int l, int r) -> void {
            if (r - l == 1) {
                info[p] = a[l];
                return;
            }
            int m = (l + r) / 2;
            self(self, 2 * p, l, m);
            self(self, 2 * p + 1, m, r);
            info[p] = info[2 * p] + info[2 * p + 1];
        };
        build(build, 1, 0, n);
    }

    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    void update(int l, int r, const Tag &v) {
        return update(1, 0, n, l, r, v);
    }
    template <std::predicate<Info> F>
    int find_first(int l, int r, F pred) {
        return find_first(1, 0, n, l, r, pred);
    }
};

struct Info {
    i64 v;
    Info(i64 _v = -1e18) : v(_v) {}
    operator i64() const { return v; }

    void apply(auto t) {
        v += t;
    }
};

Info operator+(Info l, Info r) {
    return Info(std::max(l.v, r.v));
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<std::vector<int>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        std::cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }

    std::vector<int> tour, tin(n), tout(n), sub(n + 1, 1);
    sub[n] = 0;
    auto prep = [&](auto &&self, int u, int p) -> void {
        if (~p) g[u].erase(std::ranges::find(g[u], p));
        tin[u] = tour.size();
        tour.push_back(u);
        for (auto v : g[u]) {
            self(self, v, u);
            sub[u] += sub[v];
        }
        tout[u] = tour.size();
    };
    prep(prep, 0, -1);

    BIT<i64> bit(n);
    Segtree<Info, i64> st(n);
    for (int i = n - 1; i >= 0; i--) {
        st.update(0, n, +1);
        st.modify(tin[i], 0);
    }

    std::vector<i64> ans(n);
    auto dfs = [&](auto &&self, int u, bool keep) -> void {
        int bv = n;
        for (auto v : g[u])
            if (sub[v] > sub[bv]) bv = v;
    
        for (auto v : g[u])
            if (v != bv) self(self, v, false);
    
        if (bv != n) self(self, bv, true);
    
        bit.update(u, +1);
        for (auto v : g[u]) if (v != bv) {
            for (int i = tin[v]; i < tout[v]; i++)
                bit.update(tour[i], +1);
        }

        i64 x = bit.query(u - 1);
        st.update(tin[u], tin[u] + 1, -2 * x);
        st.update(0, 1, +x);
        ans[u] = +x;

        if (!keep) {
            for (int i = tin[u]; i < tout[u]; i++)
                bit.update(tour[i], -1);
        }
    };
    dfs(dfs, 0, true);

    auto dfs2 = [&](auto &&self, int u, i64 add = 0) -> void {
        add += st.query(tin[u], tin[u] + 1);
        ans[u] += add;
        for (auto v : g[u])
            self(self, v, add);
    };
    dfs2(dfs2, 0);

    for (int i = 0; i < n; i++)
        std::cout << ans[i] << " \n"[i + 1 == n];
}

Submission Info

Judge Result