結果

問題 No.900 aδδitivee
ユーザー Navier_BoltzmannNavier_Boltzmann
提出日時 2024-01-07 16:03:30
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 365 ms / 2,000 ms
コード長 5,783 bytes
コンパイル時間 9,642 ms
コンパイル使用メモリ 354,136 KB
実行使用メモリ 26,400 KB
最終ジャッジ日時 2024-09-27 19:25:58
合計ジャッジ時間 16,501 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 320 ms
26,228 KB
testcase_08 AC 319 ms
26,236 KB
testcase_09 AC 336 ms
26,304 KB
testcase_10 AC 365 ms
26,268 KB
testcase_11 AC 357 ms
26,144 KB
testcase_12 AC 327 ms
26,204 KB
testcase_13 AC 334 ms
26,260 KB
testcase_14 AC 319 ms
26,240 KB
testcase_15 AC 323 ms
26,216 KB
testcase_16 AC 314 ms
26,204 KB
testcase_17 AC 327 ms
26,200 KB
testcase_18 AC 330 ms
26,256 KB
testcase_19 AC 326 ms
26,228 KB
testcase_20 AC 327 ms
26,140 KB
testcase_21 AC 323 ms
26,400 KB
testcase_22 AC 260 ms
26,116 KB
testcase_23 AC 260 ms
26,028 KB
testcase_24 AC 274 ms
26,020 KB
testcase_25 AC 267 ms
26,072 KB
testcase_26 AC 274 ms
26,072 KB
testcase_27 AC 263 ms
26,024 KB
testcase_28 AC 258 ms
26,140 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>


using namespace std;
using namespace atcoder;
#define rep(i,m,n,k) for (int i = (int)(m); i < (int)(n); i += (int)(k))
#define rrep(i,m,n,k) for (int i = (int)(m); i > (int)(n); i += (int)(k))
#define ll long long
#define list(T,A,N) vector<T> A(N);for(int i=0;i<(int)(N);i++){cin >> A[i];}
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
template<typename T> map<T,int> Counter(vector<T> X){map<T,int> C;for(auto x:X){C[x]++;}; return C;}

struct HLD{

    int N;
    vector<vector<int>> e;
    vector<int> par;
    vector<int> sub;
    vector<int> dist;
    vector<int> head;
    vector<int> depth;
    vector<int> ID;
    vector<int> HEAD;
    vector<int> PAR;
    vector<int> DEPTH;
    vector<int> SUB;
    
    HLD(vector<vector<int>> &_e, int root = 0){
        
        e = _e;
        N = (int)(e.size());
        par = vector<int> (N,-1);
        sub = vector<int> (N,-1);
        dist = vector<int> (N,-1);
        head = vector<int> (N,-1);
        depth = vector<int> (N,-1);
        ID = vector<int> (N,-1);
        HEAD = vector<int> (N,-1);
        PAR = vector<int> (N,-1);
        DEPTH = vector<int> (N,-1);
        SUB = vector<int> (N,-1);
        dist[root] = 0;
        deque<int> v;
        v.emplace_back(root);
        int x;
        while(!v.empty()){
            x = v.front();v.pop_front();
            for (auto ix:e[x]){
                if(dist[ix]!=-1) continue;
                dist[ix] = dist[x] + 1;
                v.emplace_back(ix);
                }
            }
        vector<pair<int,int>> H(N);
        for(int i=0;i<N;i++){
            H[i] = {-dist[i],i};
        }
        sort(H.begin(),H.end());
        int tmp;
        for(auto [h,i]:H){
            tmp = 1;
            for (auto ix:e[i]){
                if(sub[ix]==-1) par[i] = ix;
                else tmp += sub[ix];
            }
            sub[i] = tmp;
        }
        ID[root] = 0;
        vector<bool> visited(N,false);
        HEAD[0] = 0;
        head[root] = 0;
        depth[root] = 0;
        DEPTH[0] = 0;
        int cnt = 0;
        v.emplace_back(root);
        SUB[0] = N;
        vector<pair<int,int>> h;
        int flg = 0;
        int n;
        while(!v.empty()){
            x = v.front();v.pop_front();
            visited[x] = true;
            ID[x] = cnt;
            cnt ++;
            n = (int)e[x].size();
            h.resize(n);
            for(int i=0;i<n;i++){
                h[i] = {sub[e[x][i]],e[x][i]};
            }
            sort(h.begin(),h.end());
            flg = 0;
            if(x==root){
                flg = -1;
            }
            for(auto [_,ix]:h){
                flg ++;
                if(visited[ix]) continue;
                v.emplace_front(ix);
                if(flg==n-1){
                    head[ix] = head[x];
                    depth[ix] = depth[x];
                }
                else{
                    head[ix] = ix;
                    depth[ix] = depth[x] + 1;
                }
            }
        }

        
        for(int i=0;i<N;i++){
            if(par[i]==-1){
                PAR[ID[i]] == -1;
            }
            else{
                PAR[ID[i]] = ID[par[i]];
            }
            HEAD[ID[i]] = ID[head[i]];
            DEPTH[ID[i]] = depth[i];
            SUB[ID[i]] = sub[i];
        }
        }

    vector<pair<int,int>> path_query(int l, int r){
        int L = ID[l];
        int R = ID[r];
        pair<int,int> tmp;
        vector<pair<int,int>> res;
        if(DEPTH[L]<DEPTH[R]){
            L = ID[r];
            R = ID[l];
        }
        while(DEPTH[L]!=DEPTH[R]){
            tmp = {HEAD[L],L+1};
            res.emplace_back(tmp);
            L = PAR[HEAD[L]];
        }
        while (HEAD[L]!=HEAD[R]){
            tmp = {HEAD[L],L+1};
            res.emplace_back(tmp);
            tmp = {HEAD[R],R+1};
            res.emplace_back(tmp);
            L = PAR[HEAD[L]];
            R = PAR[HEAD[R]];
        }
        tmp = {min(L,R),max(L,R)+1};
        res.emplace_back(tmp);
        return res;
    }

    pair<int,int> sub_query(int k){
        int K = ID[k];
        return {K,K+SUB[K]};
    }


};


array<ll,2> ope(array<ll,2> x,array<ll,2> y){
    array<ll,2> z;
    z[0] = x[0]+y[0];
    z[1] = x[1]+y[1];
    return z;
}
array<ll,2> e_(){
    array<ll,2> z={0};
    return z;
}
array<ll,2> mapping(ll f, array<ll,2> x){
    array<ll,2> z;
    z[0] = x[0]+f*x[1];
    z[1] = x[1];
    return z;
}
ll composition(ll f,ll g){
    return f+g;
}
ll id_(){
    return 0;
}

int main(){
    int N;
    cin >> N;
    vector<vector<int>> e(N);
    vector<ll> W(N);
    int u,v;
    ll w;
    rep(_,0,N-1,1){
        cin >> u >> v >> w;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        W[v] = w;
    }
    int Q;
    cin >> Q;
    
    HLD hld(e);
    vector<int> id = hld.ID;
    vector<array<ll,2>> B(N,array<ll,2> {0});
    rep(i,0,N,1){
        B[id[i]][0] = W[i];
        B[id[i]][1] = 1;
    }
    lazy_segtree<array<ll,2>,ope,e_,ll,mapping,composition,id_> T(B);
    int flg,l,r,b,a;
    ll x,tmp;
    rep(_,0,Q,1){
        cin >> flg;
        if(flg==1){
            cin >> a >> x;
            auto [l,r] = hld.sub_query(a);
            T.apply(l+1,r,x);
        }
        else{
            cin >> b;
            tmp = 0;
            for(auto lr:hld.path_query(0,b)){
                l = lr.first;
                r = lr.second;
                tmp += T.prod(l,r)[0];
            }
            cout << tmp << endl;
        }
    }
    return 0;

}
0