結果

問題 No.1197 モンスターショー
ユーザー square1001
提出日時 2020-08-22 15:10:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,579 bytes
コンパイル時間 1,344 ms
コンパイル使用メモリ 94,160 KB
実行使用メモリ 36,256 KB
最終ジャッジ日時 2024-10-15 09:27:28
合計ジャッジ時間 7,229 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 4 RE * 3 TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifndef CLASS_FENWICKTREE
#define CLASS_FENWICKTREE
#include <vector>
#include <cassert>
#include <cstddef>
template <class type>
class fenwick_tree {
private:
    std::size_t n, sz;
    std::vector<type> val;
public:
    fenwick_tree() : n(0), sz(0) {};
    fenwick_tree(std::size_t n_) : n(n_) {
        sz = 1; while (sz < n) sz *= 2;
        val = std::vector<type>(sz + 1);
    }
    template <class InputIterator>
    fenwick_tree(InputIterator first, InputIterator last) : n(last - first) {
        sz = 1; while (sz < n) sz *= 2;
        val = std::vector<type>(sz + 1);
        std::size_t cur = 0;
        for (InputIterator it = first; it != last; ++it) val[++cur] += *it;
        for (std::size_t i = 1; i < sz; ++i) val[i + (i & ~(i - 1))] += val[i];
    }
    void add(std::size_t pos, type delta) {
        for (std::size_t i = pos + 1; i <= sz; i += i & ~(i - 1)) {
            val[i] += delta;
        }
    }
    type getsum(std::size_t r) const {
        assert(0 <= r && r <= n);
        type ans = 0;
        for (std::size_t i = r; i >= 1; i -= i & ~(i - 1)) {
            ans += val[i];
        }
        return ans;
    }
    type getsum(std::size_t l, std::size_t r) const {
        assert(0 <= l && l <= r && r <= n);
        return getsum(r) - getsum(l);
    }
    std::size_t binary_search(type threshold) const {
        std::size_t ans = 0;
        for (std::size_t i = (sz >> 1); i >= 1; i >>= 1) {
            if (threshold >= val[ans + i]) {
                threshold -= val[ans + i];
                ans += i;
            }
        }
        return ans;
    }
};
#endif // CLASS_FENWICKTREE
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> C(K);
    for (int i = 0; i < K; ++i) {
        cin >> C[i]; --C[i];
    }
    vector<vector<int> > G(N);
    for (int i = 0; i < N - 1; ++i) {
        int a, b;
        cin >> a >> b; --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    // step #1. build tree
    vector<vector<int> > child(N);
    vector<int> p(N), subtree(N, 1), depth(N);
    function<void(int, int)> build_tree_1 = [&](int pos, int pre) {
        p[pos] = pre;
        for (int i : G[pos]) {
            if (i != pre) {
                child[pos].push_back(i);
                depth[i] = depth[pos] + 1;
                build_tree_1(i, pos);
                subtree[pos] += subtree[i];
            }
        }
        sort(child[pos].begin(), child[pos].end(), [&](int i, int j) { return subtree[i] > subtree[j]; });
    };
    build_tree_1(0, 0);
    int track = 0;
    vector<int> lp(N), rp(N);
    function<void(int, int)> build_tree_2 = [&](int pos, int pre) {
        lp[pos] = track++;
        for (int i : child[pos]) {
            build_tree_2(i, pos);
        }
        rp[pos] = track;
    };
    build_tree_2(0, 0);
    // step #2. prepare for heavy-light decomposition
    int bits = 0;
    while ((1 << bits) < N) ++bits;
    vector<vector<int> > par(bits, vector<int>(N));
    par[0] = p;
    for (int i = 1; i < bits; ++i) {
        for (int j = 0; j < N; ++j) {
            par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }
    fenwick_tree<long long> fen1(N), fen2(N);
    function<void(int, int, long long)> range_add = [&](int l, int r, long long x) {
        fen1.add(l, x);
        fen1.add(r, -x);
        fen2.add(l, -l * x);
        fen2.add(r, r * x);
    };
    function<long long(int, int)> range_sum = [&](int l, int r) {
        return fen1.getsum(r) * r - fen1.getsum(l) * l + fen2.getsum(l, r);
    };
    function<void(int, int)> add = [&](int pos, int val) {
        int cdepth = depth[pos];
        while (true) {
            int nxt = pos, ndepth = cdepth;
            for (int i = bits - 1; i >= 0; --i) {
                if (ndepth >= (1 << i) && lp[par[i][nxt]] == lp[pos] - (cdepth - ndepth)) {
                    ndepth -= (1 << i);
                    nxt = par[i][nxt];
                }
            }
            range_add(lp[nxt], lp[pos] + 1, val);
            if (nxt == 0) break;
            pos = par[0][nxt];
            cdepth = ndepth - 1;
        }
    };
    function<long long(int)> sum = [&](int pos) {
        int cdepth = depth[pos];
        long long res = 0;
        while (true) {
            int nxt = pos, ndepth = cdepth;
            for (int i = bits - 1; i >= 0; --i) {
                if (ndepth >= (1 << i) && lp[par[i][nxt]] == lp[pos] - (cdepth - ndepth)) {
                    ndepth -= (1 << i);
                    nxt = par[i][nxt];
                }
            }
            res += range_sum(lp[nxt], lp[pos] + 1);
            if (nxt == 0) break;
            pos = par[0][nxt];
            cdepth = ndepth - 1;
        }
        return res;
    };
    // step #3. solve
    long long basic = 0;
    for (int i = 0; i < K; ++i) {
        add(C[i], 1);
        basic += depth[C[i]];
    }
    long long ans = 0;
    for (int i = 0; i < Q; ++i) {
        int tp;
        cin >> tp;
        if (tp == 1) {
            int x, y;
            cin >> x >> y; --x, --y;
            add(C[x], -1);
            basic -= depth[C[x]];
            C[x] = y;
            add(C[x], 1);
            basic += depth[C[x]];
        }
        else {
            int x;
            cin >> x; --x;
            long long ans = 1LL * depth[x] * K + basic;
            long long res = sum(x) - K;
            ans -= res * 2;
            cout << ans << '\n';
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0