結果

問題 No.2676 A Tourist
ユーザー NokonoKotlin
提出日時 2024-03-13 20:57:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,021 bytes
コンパイル時間 3,919 ms
コンパイル使用メモリ 269,544 KB
実行使用メモリ 231,016 KB
最終ジャッジ日時 2024-09-29 23:20:09
合計ジャッジ時間 16,242 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 -- * 1
other AC * 5 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
#include <atcoder/fenwicktree.hpp>
using namespace std;
// Vertex Add Path Sum を使ってナイーブに更新する
// クエリ 0 で O(uの次数) 時間かかるので TLE を期待
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);
    }
    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]);
    }
    // 各頂点の重み := 隣接する頂点の a の合計
    // に対して path sum を計算する
    vertex_add_path_sum neighbor_sum(N, edges);
    for (int i = 0; i < N; i++) {
        for (auto&& v : adj[i]) {
            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);
            for (auto&& v : adj[u]) {
                neighbor_sum.add(v, x);
            }
            continue;
        }
        if (t == 1) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            ll ans = neighbor_sum.sum(u, v);
            ans -= a_sum.sum(u, v);
            ans += a[u] + a[v];
            cout << ans << "\n";
            continue;
        }
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0