結果

問題 No.2439 Fragile Apple Tree
ユーザー noya2noya2
提出日時 2023-08-15 14:45:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,654 ms / 10,000 ms
コード長 6,623 bytes
コンパイル時間 2,963 ms
コンパイル使用メモリ 233,392 KB
実行使用メモリ 106,688 KB
最終ジャッジ日時 2024-05-06 07:36:39
合計ジャッジ時間 39,854 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,153 ms
52,596 KB
testcase_01 AC 2,119 ms
75,712 KB
testcase_02 AC 2,005 ms
75,840 KB
testcase_03 AC 962 ms
106,688 KB
testcase_04 AC 1,295 ms
106,564 KB
testcase_05 AC 1,932 ms
75,592 KB
testcase_06 AC 2,051 ms
75,588 KB
testcase_07 AC 2,654 ms
76,228 KB
testcase_08 AC 2,639 ms
76,224 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2,519 ms
74,400 KB
testcase_15 AC 1,397 ms
75,712 KB
testcase_16 AC 1,974 ms
75,584 KB
testcase_17 AC 1,903 ms
75,588 KB
testcase_18 AC 782 ms
51,748 KB
testcase_19 AC 660 ms
27,580 KB
testcase_20 AC 276 ms
24,528 KB
testcase_21 AC 88 ms
5,376 KB
testcase_22 AC 1,069 ms
40,448 KB
testcase_23 AC 474 ms
21,316 KB
testcase_24 AC 560 ms
26,148 KB
testcase_25 AC 535 ms
45,820 KB
testcase_26 AC 665 ms
49,900 KB
testcase_27 AC 478 ms
39,180 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 1,152 ms
76,108 KB
testcase_32 AC 1,142 ms
76,228 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/lazysegtree>
using namespace std;
using namespace atcoder;

struct hldTree {
    hldTree (int _n = 0, int _root = 0) : n(_n), root(_root) { init();}
    void add_edge(int u, int v, int id){ // id must be 0 <= id < n
        es[u].emplace_back(v,id);
        es[v].emplace_back(u,id);
    }
    void build(){
        dfs_init(root);
        int t = 0;
        dfs_hld(root,t);
    }
    int lca(int u, int v){
        while (nxt[u] != nxt[v]){
            if (down[u] < down[v]) swap(u,v);
            u = par[nxt[u]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    int depth(int v){ return dep[v];}
    int pre(int v){ return down[v];}
    int post(int v){ return up[v];}
    int ord(int i){ return order[i];}
    template<typename F>
    void path_query(int u, int v, bool vertex, const F &f){ // f is function takes (left, right) as argument, range = [left,right).
        int l = lca(u,v);
        for (auto &p : ascend(u,l)){
            int s = p.first + 1, t = p.second; // p.first + 1 : depth(p.first) > depth(p.second), so [p.second,p.first] = [p.second,p.first+1)
            s > t ? f(t,s) : f(s,t);
        }
        if (vertex) f(down[l],down[l]+1); // vertex is true : query is for point 
        for (auto &p : descend(l,v)){
            int s = p.first, t = p.second + 1; // p.second +1 : depth(p.first) < depth(p.second), so [p.first,p.second] = [p.first,p.second+1)
            s > t ? f(t,s) : f(s,t);
        }
    }
    template<typename F>
    void subtree_query(int v, bool vertex, const F &f){
        f(down[v] + (vertex ? 0 : 1), up[v]);
    }
    const vector<pair<int,int>>& operator()(int idx) const { return es[idx];}
  private:
    int n, root;
    vector<vector<pair<int,int>>> es;
    vector<int> size, par, dep, up, down, nxt; // nxt[i] : most shallow vertex in connected component of vertex i
    vector<int> order; // order[i] is ith vertex visited on Euler tour, vertex v has edges[v] (root has no edge)
    void init(){
        es.resize(n);
        size.resize(n,0);
        par.resize(n,root);
        dep.resize(n,0);
        up.resize(n,-1);
        down.resize(n,-1);
        nxt.resize(n,root);
        order.resize(n,-1);
    }
    void dfs_init(int cur){
        size[cur] = 1;
        for (auto &e : es[cur]){
            if (e.first == par[cur]){
                if (es[cur].size() >= 2 && e.first == es[cur][0].first){
                    swap(es[cur][0],es[cur][1]); // if cur is not leaf, vs[cur][0] is not cur's parent
                }
                else continue;
            }
            par[e.first] = cur;
            dep[e.first] = dep[cur] + 1;
            dfs_init(e.first);
            size[cur] += size[e.first];
            if (size[e.first] > size[es[cur][0].first]){
                swap(e,es[cur][0]); // to maximize vs[cur][0]'s subtree_size
            }
        }
    }
    void dfs_hld(int cur, int &tnow){
        down[cur] = tnow++; // down[0,...,n-1] is permutation of 0,...,n-1
        order[down[cur]] = cur; 
        for (auto e : es[cur]){
            if (e.first == par[cur]) continue;
            nxt[e.first] = (e.first == es[cur][0].first ? nxt[cur] : e.first);
            dfs_hld(e.first,tnow);
        }
        up[cur] = tnow; // up[0,...,n-1] is NOT permutation, up[*] <= n
    }
    vector<pair<int,int>> ascend(int u, int v) const { // [u,v), depth[u] > depth[v]
        vector<pair<int,int>> res;
        while (nxt[u] != nxt[v]){
            res.emplace_back(down[u],down[nxt[u]]); // [s1,t1], [s2,t2], ...
            u = par[nxt[u]];
        }
        if (u != v) res.emplace_back(down[u],down[v]+1); // [s,t). v is not in the range (down[] is ordered opposite direction of depth)
        return res;
    }
    vector<pair<int,int>> descend(int u, int v) const { // (u,v], depth[u] < depth[v]
        if (u == v) return {};
        if (nxt[u] == nxt[v]){
            return {pair<int,int>(down[u]+1,down[v])}; // (s,t]. u is not in the range
        }
        vector<pair<int,int>> res = descend(u,par[nxt[v]]);
        res.emplace_back(down[nxt[v]],down[v]); // [s1,t1], [s2,t2], ...
        return res;
    }
};

using ll = long long;
using ar = array<ll,2>;
const ll linf = 1e16;
hldTree g;

ar op1(ar a, ar b){
    if (a[0] <= 0 && b[0] <= 0){
        return (g.depth(a[1]) > g.depth(b[1]) ? a : b);
    }
    return (a[0] < b[0] ? a : b);
}
ar e1(){
    return {linf,0};
}
ar mapping1(ll f, ar x){
    return {x[0]+f,x[1]};
}
ll composition1(ll f, ll g){
    return f + g;
}
ll ideal1(){
    return 0;
}

ar op2(ar a, ar b){
    return {a[0]+b[0],a[1]+b[1]};
}
ar e2(){
    return {0,0};
}
ar mapping2(int f, ar x){
    if (f == -1) return x;
    return {0,0};
}
int composition2(int f, int g){
    if (f == -1) return g;
    return f;
}
int ideal2(){
    return -1;
}

int main(){
    int n, q; cin >> n >> q;
    vector<ll> cs(n-1);
    g = hldTree(n);
    for (int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v >> cs[i]; u--, v--;
        g.add_edge(u,v,i);
    }
    g.build();
    lazy_segtree<ar,op1,e1,ll,mapping1,composition1,ideal1> seg1(n);
    lazy_segtree<ar,op2,e2,int,mapping2,composition2,ideal2> seg2(n);
    for (int v = 0; v < n; v++){
        for (auto [u, id] : g(v)){
            if (g.depth(v) > g.depth(u)) continue;
            seg1.set(g.pre(u),{cs[id],u});
        }
        seg2.set(g.pre(v),{1,0});
    }
    ll num = 0;
    auto add = [&](int l, int r){
        if (l > r) swap(l,r);
        seg1.apply(l,r,num);
    };
    ar dele = e1();
    auto del_edge = [&](int l, int r){
        if (l > r) swap(l,r);
        dele = op1(dele,seg1.prod(l,r));
    };
    ar sum = e2();
    auto count = [&](int l, int r){
        if (l > r) swap(l,r);
        sum = op2(sum,seg2.prod(l,r));
    };
    auto update = [&](int l, int r){
        if (l > r) swap(l,r);
        seg2.apply(l,r,0);
    };
    while (q--){
        int t; cin >> t;
        if (t == 2){
            cout << seg2.all_prod()[0] << endl;
            continue;
        }
        int v; cin >> v; v--;
        ll x; cin >> x;
        // add apple
        seg2.set(g.pre(v),{1,seg2.get(g.pre(v))[1]+x});
        // decrease by x
        num = -x;
        g.path_query(0,v,false,add);
        // find deleted edge
        dele = e1();
        g.path_query(0,v,false,del_edge);
        if (dele[0] > 0) continue;
        // delete the edge
        int f = dele[1];
        sum = e2();
        g.subtree_query(f,true,count);
        g.subtree_query(f,true,update);
        // increase by sum[1] : droped apples
        num = sum[1];
        g.path_query(0,v,false,add);
    }
}
0