結果

問題 No.2676 A Tourist
ユーザー nu50218nu50218
提出日時 2024-02-13 20:00:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,016 bytes
コンパイル時間 2,578 ms
コンパイル使用メモリ 226,472 KB
実行使用メモリ 249,616 KB
最終ジャッジ日時 2024-09-29 23:09:53
合計ジャッジ時間 29,188 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 264 ms
76,176 KB
testcase_02 AC 885 ms
230,940 KB
testcase_03 AC 848 ms
230,996 KB
testcase_04 AC 856 ms
230,868 KB
testcase_05 AC 855 ms
230,992 KB
testcase_06 AC 260 ms
76,792 KB
testcase_07 AC 1,077 ms
232,628 KB
testcase_08 AC 451 ms
232,620 KB
testcase_09 AC 861 ms
232,632 KB
testcase_10 AC 501 ms
232,632 KB
testcase_11 AC 560 ms
215,920 KB
testcase_12 AC 230 ms
82,384 KB
testcase_13 AC 697 ms
249,612 KB
testcase_14 AC 666 ms
249,612 KB
testcase_15 AC 693 ms
249,616 KB
testcase_16 AC 270 ms
76,692 KB
testcase_17 AC 933 ms
232,768 KB
testcase_18 AC 856 ms
232,768 KB
testcase_19 AC 1,028 ms
232,648 KB
testcase_20 AC 956 ms
231,212 KB
testcase_21 AC 29 ms
5,248 KB
testcase_22 AC 28 ms
5,248 KB
testcase_23 AC 13 ms
5,248 KB
testcase_24 AC 27 ms
5,248 KB
testcase_25 AC 7 ms
5,248 KB
testcase_26 AC 1 ms
5,248 KB
testcase_27 AC 196 ms
76,192 KB
testcase_28 AC 696 ms
232,696 KB
testcase_29 AC 464 ms
232,572 KB
testcase_30 AC 662 ms
232,700 KB
testcase_31 AC 611 ms
232,692 KB
testcase_32 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <atcoder/fenwicktree.hpp>
using namespace std;

// 解説の計算を、次数で平方分割する

template <class S, S (*op)(S, S)>
struct sparse_table {
   public:
    sparse_table() {}

    sparse_table(const std::vector<S>& v) : _n(int(v.size())) {
        int max_log = 0;

        log_table.resize(_n + 1);
        log_table[1] = 0;
        for (int i = 2; i < _n + 1; i++) {
            log_table[i] = log_table[i >> 1] + 1;
            max_log = log_table[i];
        }

        table.resize(max_log + 1);
        for (int i = 0; i <= max_log; i++) {
            table[i].resize(_n);
        }
        for (int j = 0; j < _n; j++) {
            table[0][j] = v[j];
        }

        for (int i = 1; i <= max_log; i++) {
            for (int j = 0; j < _n; j++) {
                if (j + (1 << (i - 1)) >= _n)
                    continue;
                table[i][j] = op(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    S query(int l, int r) {
        assert(0 <= l && l < _n);
        assert(0 < r && r <= _n);
        assert(l < r);

        int i = log_table[r - l];
        return op(table[i][l], table[i][r - (1 << i)]);
    }

   private:
    int _n;
    std::vector<int> log_table;
    std::vector<std::vector<S>> table;
};

// returns a list of (vertex, depth) pairs
inline std::vector<std::pair<int, int>> euler_tour(const int n, const std::vector<std::pair<int, int>>& edges, const int root = 0) {
    std::vector<int> adj[n];
    for (auto&& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    std::vector<std::pair<int, int>> ret;

    std::function<void(int, int, int)> dfs = [&](int v, int p = -1, int d = 0) -> void {
        for (auto&& u : adj[v]) {
            if (u != p) {
                ret.push_back({v, d});
                dfs(u, v, d + 1);
            }
        }
        ret.push_back({v, d});
    };

    dfs(root, -1, 0);

    return ret;
}

namespace nu50218 {
inline std::pair<int, int> lca_st_op(std::pair<int, int> x, std::pair<int, int> y) {
    return min(x, y);
}
};  // namespace nu50218

struct LCA {
    int lca(int u, int v) {
        if (idx[u] > idx[v]) std::swap(u, v);
        return st.query(idx[u], idx[v] + 1).second;
    }

    int depth(int v) {
        return dep[v];
    }

    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }

    LCA(const int n, const std::vector<std::pair<int, int>>& edges, const int root = 0) {
        dep.resize(n);
        idx.resize(n);

        auto tour = euler_tour(n, edges, root);

        std::vector<std::pair<int, int>> a(tour.size());

        for (int i = 0; i < (int)tour.size(); i++) {
            auto [v, d] = tour[i];
            dep[v] = d;
            idx[v] = i;
            a[i] = {d, v};
        }

        st = sparse_table<std::pair<int, int>, nu50218::lca_st_op>(a);
    }

   private:
    std::vector<int> dep;
    std::vector<int> idx;
    inline std::pair<int, int> op(std::pair<int, int> x, std::pair<int, int> y) {
        return min(x, y);
    }
    sparse_table<std::pair<int, int>, nu50218::lca_st_op> st;
};

template <typename T = long long>
struct vertex_add_path_sum {
    vertex_add_path_sum(const int n, const std::vector<std::pair<int, int>>& edges) : n(n), index(n), fwt(2 * n + 1), lca(n, edges, 0) {
        std::vector<std::vector<int>> adj(n);
        for (auto&& [u, v] : edges) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        int i = 1;

        std::function<void(int, int)> dfs = [&](int v, int p = -1) -> void {
            index[v].first = i++;
            for (auto&& u : adj[v]) {
                if (u != p) {
                    dfs(u, v);
                }
            }
            index[v].second = i++;
        };

        dfs(0, -1);
    }

    void add(int p, T x) {
        fwt.add(index[p].first, x);
        fwt.add(index[p].second, -x);
    }

    T sum(int u, int v) {
        auto sub = index[lca.lca(u, v)].first;
        return fwt.sum(0, index[u].first + 1) + fwt.sum(0, index[v].first + 1) - fwt.sum(0, sub) - fwt.sum(0, sub + 1);
    }

   private:
    int n;
    std::vector<std::pair<int, int>> index;
    atcoder::fenwick_tree<T> fwt;
    LCA lca;
};

using ll = long long;

// sqrt(200000)
const int border = 447;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<ll> a(N);
    for (auto&& x : a) {
        cin >> x;
    }

    vector<pair<int, int>> edges;
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        edges.emplace_back(u, v);
    }

    vector<vector<int>> adj(N);
    for (auto&& [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    vector<int> heavy_vertices;
    for (int i = 0; i < N; i++) {
        if ((int)adj[i].size() > border) {
            heavy_vertices.push_back(i);
        }
    }

    LCA lca(N, edges);

    // a の path sum を計算する
    vertex_add_path_sum a_sum(N, edges);
    for (int i = 0; i < N; i++) {
        a_sum.add(i, a[i]);
    }

    // 各頂点の重み := 隣接する「次数が border 以下」頂点の a の合計
    // に対して path sum を計算する
    vertex_add_path_sum low_deg_neighbor_sum(N, edges);
    for (int i = 0; i < N; i++) {
        if ((int)adj[i].size() <= border) {
            for (auto&& v : adj[i]) {
                low_deg_neighbor_sum.add(v, a[i]);
            }
        }
    }

    for (int q = 0; q < Q; q++) {
        int t;
        cin >> t;

        if (t == 0) {
            int u;
            ll x;
            cin >> u >> x;
            u--;

            a[u] += x;
            a_sum.add(u, x);

            // 次数が小さい頂点は愚直に反映する
            if ((int)adj[u].size() <= border) {
                for (auto&& v : adj[u]) {
                    low_deg_neighbor_sum.add(v, x);
                }
            }

            continue;
        }

        if (t == 1) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;

            ll ans = low_deg_neighbor_sum.sum(u, v);
            ans -= a_sum.sum(u, v);
            ans += a[u] + a[v];

            // 次数が大きい頂点が u-v パスの近くにあったら調整する
            for (auto&& h : heavy_vertices) {
                int dist_uv = lca.dist(u, v);
                int dist_uh = lca.dist(u, h);
                int dist_hv = lca.dist(h, v);

                // h がパスの頂点に隣接している
                if (dist_uv + 2 >= dist_uh + dist_hv) {
                    ans += a[h];
                }
                // h がパスの2頂点に隣接している
                if (dist_uv == dist_uh + dist_hv && h != u && h != v) {
                    ans += a[h];
                }
            }

            cout << ans << "\n";
            continue;
        }
    }
}
0