結果

問題 No.2676 A Tourist
ユーザー umimelumimel
提出日時 2024-03-16 14:33:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,274 ms / 5,000 ms
コード長 7,096 bytes
コンパイル時間 2,923 ms
コンパイル使用メモリ 198,896 KB
実行使用メモリ 66,948 KB
最終ジャッジ日時 2024-03-16 14:33:26
合計ジャッジ時間 22,191 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 276 ms
18,048 KB
testcase_02 AC 1,116 ms
46,268 KB
testcase_03 AC 464 ms
46,268 KB
testcase_04 AC 602 ms
46,268 KB
testcase_05 AC 754 ms
46,268 KB
testcase_06 AC 144 ms
17,236 KB
testcase_07 AC 521 ms
43,600 KB
testcase_08 AC 171 ms
43,600 KB
testcase_09 AC 403 ms
43,600 KB
testcase_10 AC 199 ms
43,600 KB
testcase_11 AC 709 ms
42,460 KB
testcase_12 AC 178 ms
24,832 KB
testcase_13 AC 622 ms
66,948 KB
testcase_14 AC 274 ms
66,948 KB
testcase_15 AC 416 ms
66,948 KB
testcase_16 AC 305 ms
18,048 KB
testcase_17 AC 1,274 ms
46,296 KB
testcase_18 AC 473 ms
46,332 KB
testcase_19 AC 1,098 ms
46,328 KB
testcase_20 AC 798 ms
46,276 KB
testcase_21 AC 34 ms
6,676 KB
testcase_22 AC 34 ms
6,676 KB
testcase_23 AC 16 ms
6,676 KB
testcase_24 AC 34 ms
6,676 KB
testcase_25 AC 9 ms
6,676 KB
testcase_26 AC 2 ms
6,676 KB
testcase_27 AC 135 ms
18,048 KB
testcase_28 AC 496 ms
43,356 KB
testcase_29 AC 171 ms
43,356 KB
testcase_30 AC 466 ms
43,356 KB
testcase_31 AC 371 ms
43,356 KB
testcase_32 AC 214 ms
66,896 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define drep(i, cc, n) for (ll i = (cc); i <= (n); ++i)
#define rep(i, n) drep(i, 0, n - 1)
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define fi first
#define se second
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const ll MOD1000000007 = 1000000007;
const ll MOD998244353 = 998244353;
const ll MOD[3] = {999727999, 1070777777, 1000000007};
const ll LINF = 1LL << 60LL;
const int IINF = (1 << 30) - 1;


template<typename T>
struct edge{
    int from, to;
    T cost;
    int id;

    edge(){}
    edge(int to, T cost=1) : from(-1), to(to), cost(cost){}
    edge(int to, T cost, int id) : from(-1), to(to), cost(cost), id(id){}
    edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}
};

template<typename T>
struct redge{
    int from, to;
    T cap, cost;
    int rev;
    
    redge(int to, T cap, T cost=(T)(1)) : from(-1), to(to), cap(cap), cost(cost){}
    redge(int to, T cap, T cost, int rev) : from(-1), to(to), cap(cap), cost(cost), rev(rev){}
};

template<typename T> using Edges = vector<edge<T>>;
template<typename T> using weighted_graph = vector<Edges<T>>;
template<typename T> using tree = vector<Edges<T>>;
using unweighted_graph = vector<vector<int>>;
template<typename T> using residual_graph = vector<vector<redge<T>>>;


template<typename W>
struct vertex_add_path_sum{
    struct segtree{
        int n;
        vector<W> dat;

        segtree(){};
        segtree(int n_){
            n = 1;
            while(n < n_) n*=2;
            dat.resize(2*n, 0);
        }

        void update(int k, W a){
            k += n-1;
            dat[k] += a;
            while(k > 0){
                k = (k-1)/2;
                dat[k] = dat[2*k+1]+dat[2*k+2];
            }
        }

        // sum of [a, b)
        W query(int a, int b){return query_sub(a, b, 0, 0, n);}

        W query_sub(int a, int b, int k, int l, int r){
            if(r <= a || b <= l){
                return 0;
            }else if(a <= l && r <= b){
                return dat[k];
            }else{
                W vl = query_sub(a, b, 2*k+1, l, (l+r)/2);
                W vr = query_sub(a, b, 2*k+2, (l+r)/2, r);
                return vl+vr;
            }
        }
    } seg;

    struct lowest_common_ancestor{
        int root = 0;
        int n;
        int log_n = 1;
        vector<vector<int>> par;
        vector<int> depth;

        lowest_common_ancestor(){}
        lowest_common_ancestor(tree<W> &T, int root = 0) : root(root){
            n = (int)T.size();
            while((1 << log_n) < n) log_n++;
            par.resize(log_n, vector<int>(n, -1));
            depth.resize(n, 0);
            init(T);
        }

        void init(tree<W> &T){
            function<void(int, int)> dfs = [&](int v, int p){
                par[0][v] = p;
                for(edge<W> e : T[v]) if(e.to!=p){
                    depth[e.to] = depth[v]+1;
                    dfs(e.to, v);
                }
            }; dfs(root, -1);

            for(int k=0; k+1<log_n; k++){
                for(int v=0; v<n; v++){
                    if(par[k][v]<0) par[k+1][v] = -1;
                    else par[k+1][v] = par[k][par[k][v]];
                }
            }
        }

        int query(int u, int v){
            if(depth[u] < depth[v]) swap(u, v);
            for(int k=0; k<log_n; k++) if((depth[u]-depth[v]) >> k & 1) u = par[k][u];

            if(u == v) return u;
            for(int k=log_n-1; k>=0; k--){
                if(par[k][u] != par[k][v]){
                    u = par[k][u];
                    v = par[k][v];
                }
            }

            return par[0][u];
        }
    } lca;

    int n;
    vector<int> par;
    vector<int> pos;
    vector<int> depth;
    vector<int> path_top;

    vertex_add_path_sum(tree<W> &T, int root = 0){
        n = (int)T.size();
        par.resize(n, 0);
        pos.resize(n, 0);
        depth.resize(n, 0);
        path_top.resize(n, -1);

        init(T, root);
    }

    void init(tree<W> &T, int root){
        vector<int> siz(n, 1);
        
        //par, siz, depthを計算
        function<void(int, int)> dfs1 = [&](int v, int p){
            par[v] = p;
            for(edge<W> e : T[v]) if(e.to!=p){
                depth[e.to] = depth[v]+1;
                dfs1(e.to, v);
                siz[v] += siz[e.to];
            }
        }; dfs1(root, -1);

        //heavy-light decomposition
        int cnt = 0;
        function<void(int, int, int)> dfs2 = [&](int v, int p, int a){
            pos[v] = cnt++;
            path_top[v] = a;

            int M = 0;
            int ch = -1;
            for(edge<W> e : T[v]) if(e.to!=p){
                if(siz[e.to] > M){
                    M = siz[e.to];
                    ch = e.to;
                }
            }
            if(ch!=-1) dfs2(ch, v, a);

            for(edge<W> e : T[v]) if(e.to!=p && e.to!=ch) dfs2(e.to, v, e.to);
        };

        dfs2(root, -1, root);
        seg = segtree(n);
        lca = lowest_common_ancestor(T, root);
    }

    vector<pair<int, int>> hld_query(int u, int v){
        vector<pair<int, int>> ret;

        int r = lca.query(u, v);
        while(path_top[u] != path_top[r]){
            ret.push_back({pos[path_top[u]], pos[u]});
            u = par[path_top[u]];
        }
        while(path_top[v] != path_top[r]){
            ret.push_back({pos[path_top[v]], pos[v]});
            v = par[path_top[v]];
        }
        ret.push_back({min(pos[u], pos[v]), max(pos[u], pos[v])});
        return ret;
    }

    void update(int v, W x){
        seg.update(pos[v], x);
    }

    W query(int u, int v){
        vector<pair<int, int>> hld = hld_query(u, v);
        W ans = 0;
        for(pair<int, int> p : hld) ans += seg.query(p.fi, p.se+1);

        return ans;
    }
};

void solve(){
    int n, q; cin >> n >> q;
    vector<ll> a(n+1, 0);
    for(int i=0; i<n; i++) cin >> a[i];
    tree<ll> T(n+1);
    T[0].push_back(edge<ll>(n));
    T[n].push_back(edge<ll>(0));
    for(int i=0; i<n-1; i++){
        int u, v; cin >> u >> v;
        u--; v--;
        T[u].push_back(edge<ll>(v));
        T[v].push_back(edge<ll>(u));
    }

    vertex_add_path_sum<ll> hld(T, n);
    //初期化
    function<void(int, int)> dfs = [&](int v, int p){
        ll sum = 0;
        for(edge<ll> e : T[v]) if(e.to != p){
            sum += a[e.to];
            dfs(e.to, v);
        }
        hld.update(v, sum);
    }; dfs(n, -1);

    while(q--){
        int type; cin >> type;
        if(type==0){
            int v, x; cin >> v >> x;
            v--;
            hld.update(hld.par[v], x);
            a[v] += x;
        }
        if(type==1){
            int u, v; cin >> u >> v;
            u--; v--;
            int r = hld.lca.query(u, v);
            cout << hld.query(u, v) + a[r] + a[hld.par[r]] << '\n';
        }
    }
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int T=1;
    //cin >> T;
    while(T--) solve();
}
0