結果

問題 No.2439 Fragile Apple Tree
コンテスト
ユーザー kenken714
提出日時 2023-08-12 04:27:41
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,845 bytes
コンパイル時間 1,921 ms
コンパイル使用メモリ 165,748 KB
実行使用メモリ 73,688 KB
最終ジャッジ日時 2024-11-22 12:49:08
合計ジャッジ時間 40,207 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#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

vector<int> g[300010];
int ans;
int sz[300010], par[300010], a[300010], b[300010];
ll c[300010], cv[300010], co[300010];

void dfs(int v, int p){
    sz[v] = 1;
    for(auto nv : g[v]){
        if(nv == p)continue;
        dfs(nv, v);
        sz[v] += sz[nv];
        par[nv] = v;
    }
}
int main(){
    ll N, Q;
    cin >> N >> Q;
    REP(i, N - 1){
        cin >> a[i] >> b[i];
        a[i]--;b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
        cin >> cv[i];
    }
    ans = N;
    dfs(0, -1);
    REP(i, N - 1){
        if(par[a[i]] == b[i])co[a[i]] = c[a[i]] = cv[i];
        else co[b[i]] = c[b[i]] = cv[i];
    }
    REP(i, Q){
        ll t;
        cin >> t;
        if(t == 1){
            ll v, x;
            cin >> v >> x;
            v--;
            int nowv = v;
            while(nowv != 0){
                c[nowv] -= x;
                if(c[nowv] <= 0){
                    ans -= sz[nowv];

                    int nev = par[nowv];
                    while(nev != 0){
                        sz[nev] -= sz[nowv];
                        c[nev] += co[nowv] - (c[nowv] + x);
                        nev = par[nev];
                    }
                    break;
                }
                nowv = par[nowv];
            }
        }
        else{
            cout << ans << endl;
        }
    }
}
0