結果

問題 No.2439 Fragile Apple Tree
ユーザー kenken714kenken714
提出日時 2023-08-12 04:27:41
言語 C++11
(gcc 11.4.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,845 bytes
コンパイル時間 1,476 ms
コンパイル使用メモリ 165,892 KB
実行使用メモリ 69,888 KB
最終ジャッジ日時 2024-05-02 02:54:47
合計ジャッジ時間 17,145 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 400 ms
69,888 KB
testcase_01 AC 679 ms
31,744 KB
testcase_02 AC 679 ms
31,744 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

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