結果

問題 No.2439 Fragile Apple Tree
コンテスト
ユーザー kenken714
提出日時 2023-08-11 19:37:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,054 ms / 10,000 ms
コード長 7,951 bytes
コンパイル時間 2,505 ms
コンパイル使用メモリ 216,068 KB
最終ジャッジ日時 2025-02-16 00:50:23
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1ll << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD (ll)1000000007


struct LazySegTree { //参照は i + sz - 1
    ll sz;
    vector<ll> node, lazy;
    vector<bool> lazyFlag;
    LazySegTree(ll n) {
        sz = 1;
        while (sz < n) sz *= 2;
        node.resize(2 * sz - 1, INF);//
        lazy.resize(2 * sz - 1);//
        lazyFlag.resize(2 * sz - 1);
    }
    void eval(ll k, ll l, ll r) {
        if (lazyFlag[k]) {
            node[k] += lazy[k];//
            if (r - l > 1) {
                lazy[2 * k + 1] += lazy[k];//
                lazy[2 * k + 2] += lazy[k];//
                lazyFlag[2 * k + 1] = lazyFlag[2 * k + 2] = true;
            }
            lazyFlag[k] = false;
            lazy[k] = 0;//
        }
    }
    void update(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) r = sz;
        eval(k, l, r);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[k] = x;//
            lazyFlag[k] = true;
            eval(k, l, r);

        }
        else {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = min(node[2 * k + 1], node[2 * k + 2]);//
        }
    }
    void update(ll a, ll x) {
        update(a, a + 1, x);
    }
    ll query(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) r = sz;
        eval(k, l, r);
        if (b <= l || r <= a) return INF;//
        if (a <= l && r <= b) return node[k];
        ll vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return min(vl, vr);//
    }
    int nibutan_query(ll a, ll b){
        ll res = nibutan(a, b);
        return (res == a - 1) ? -1 : res;
    }
    ll nibutan(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) r = sz;
        eval(k, l, r);
        if (node[k] > 0 or r <= a or b <= l) {
            return a - 1;
        } 
        else if (r - l == 1) {
            return (k - (sz - 1));
        } 
        else {
            int vr = nibutan(a, b, 2 * k + 2, (l + r) / 2, r);
            
            if (vr != a - 1) {  
                return vr;
            } else {  
                return nibutan(a, b, 2 * k + 1, l, (l + r) / 2);
            }
        }
    }
    void init() {
        REPR(i, sz - 2) node[i] = min(node[2 * i + 1], node[2 * i + 2]);//
    }
};


struct SegTree {
    ll sz;
    vector<ll> dat;
    SegTree(ll n) {
        sz = 1;
        while (sz < n)sz *= 2;
        dat.resize(2 * sz - 1, 0);//
    }
    void update(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1) {
        if (r < 0) r = sz;
        if (r <= a or b <= l)return;//
        if (a <= l and r <= b) {
            dat[k] += x;
            return;
        } //
        ll q1, q2;
        update(a, b, x, k * 2 + 1, l, (l + r) / 2);
        update(a, b, x, k * 2 + 2, (l + r) / 2, r);
    }
    ll query(ll a){
        a += sz - 1;
        ll res = 0;
        do{
            res += dat[a];
            a = (a - 1) / 2;
        } while (a > 0);
        return res;
    }
};

struct HLD {
    vector<ll> g[510000];
    vector<ll> sz, in, out, head, rev, par, dep; //rev = in -> index
    HLD(ll n) : sz(n), in(n), out(n), head(n), rev(n), par(n), dep(n) {};
    void dfs_sz(ll a, ll p, ll b) {
        par[a] = p;
        sz[a] = 1;
        dep[a] = b;
        if (g[a].size() && g[a][0] == p) swap(g[a][0], g[a].back());
        for (auto& to : g[a]) {
            if (to == p)continue;
            dfs_sz(to, a, b + 1);
            sz[a] += sz[to];
            if (sz[g[a][0]] < sz[to])swap(g[a][0], to);
        }
    }
    void dfs_hld(ll a, ll p, ll& t) {
        in[a] = t++;
        rev[in[a]] = a;
        for (auto& to : g[a]) {
            if (to == p)continue;
            head[to] = (g[a][0] == to ? head[a] : to);
            dfs_hld(to, a, t);
        }
        out[a] = t;
    }
    void edgeset(ll a, ll b) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    void build() {
        dfs_sz(0, -1, 0);
        ll t = 0;
        dfs_hld(0, -1, t);
    }
    void input(ll n) {
        REP(i, n - 1) {
            ll a, b;
            cin >> a >> b;
            a--; b--;
            edgeset(a, b);
        }
        build();
    }
    ll la(ll a, ll x) {
        while (1) {
            ll h = head[a];
            if (in[a] - x >= in[h])return rev[in[a] - x];
            x -= in[a] - in[h] + 1;
            a = par[h];
        }
    }
    ll lca(ll a, ll b) {
        for (;; b = par[head[b]]) {
            if (in[a] > in[b])swap(a, b);
            if (head[a] == head[b])return a;
        }
    }
    template< typename Q, typename F >
    ll query(ll a, ll b, ll ti, const Q& q, const F& f, bool edge = false) {
        ll l = ti, r = ti;
        for (;; b = par[head[b]]) {
            if (in[a] > in[b])swap(a, b), swap(l, r);
            if (head[a] == head[b])break;
            l = f(q(in[head[b]], in[b] + 1), l);
        }
        return f(f(q(in[a] + edge, in[b] + 1), l), r);
    }
    template< typename Q >
    ll nibutan(ll a, ll b, const Q& q, bool edge = false) {
        for (;; b = par[head[b]]) {
            if (in[a] > in[b]) swap(a, b);
            if (head[a] == head[b])break;
            ll res = q(in[head[b]], in[b] + 1);
            if (res != -1) return rev[res];
        }
        ll res = q(in[a] + edge, in[b] + 1);
        if(res != -1)return rev[res];
        return -1;
    }
    template < typename Q >
    void addpath(ll a, ll b, ll x, const Q& q, bool edge = false) { //path
        for (;; b = par[head[b]]) {
            if (in[a] > in[b])swap(a, b);
            if (head[a] == head[b])break;
            q(in[head[b]], in[b] + 1, x);
        }
        return q(in[a] + edge, in[b] + 1, x);
    }
    template < typename Q >
    void addst(ll a, ll x, const Q& q) { //subtree
        q(in[a], out[a], x);
    }
};

int ans;
LazySegTree seg(300010);
SegTree seg2(300010);
HLD hld(300010);
struct Edge{
    ll a, b, c;
};

vector<Edge> edges;
vector<ll> init_c;
int main(){
    ll N, Q;
    cin >> N >> Q;
    ans = N;
    edges.resize(N - 1);
    init_c.resize(N);
    for(int i = 0; i < N - 1; i++){
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
        edges[i].a--;
        edges[i].b--;
        hld.edgeset(edges[i].a, edges[i].b);
    }
    hld.build();
    
    //init
    for (int i = 0; i < N - 1; i++){
        if(hld.dep[edges[i].a] > hld.dep[edges[i].b]) swap(edges[i].a, edges[i].b);
        seg.node[hld.in[edges[i].b] + seg.sz - 1] = edges[i].c;
        init_c[edges[i].b] = edges[i].c;
    }
    init_c[0] = INF;
    seg.node[hld.in[0] + seg.sz - 1] = INF;
    seg.init();
    for(int i = 0; i < N; i++){
        seg2.dat[hld.in[i] + seg2.sz - 1] = hld.sz[i];
    }

    for(int i = 0; i < Q; i++){
        ll type;
        cin >> type;
        if(type == 1){
            ll v, x;
            cin >> v >> x;
            v--;
            hld.addpath(0, v, -x, [](ll a, ll b, ll x){seg.update(a, b, x);});
            ll w = hld.nibutan(0, v, [](ll a, ll b){return seg.nibutan_query(a, b);});
            if(w == -1)continue;
            ll subtree_sz = seg2.query(hld.in[w]);
            ans -= subtree_sz;
            hld.addpath(0, hld.par[w], -subtree_sz, [](ll a, ll b, ll x){seg2.update(a, b, x);});
            ll w_apple = init_c[w] - hld.query(w, w, 0, [](ll a, ll b){return seg.query(a, b);}, [](ll a, ll b){return min(a, b);});
            hld.addpath(0, w, w_apple, [](ll a, ll b, ll x){seg.update(a, b, x);});
        }
        if(type == 2){
            cout << ans << endl;
        }
    }
}
0