結果

問題 No.900 aδδitivee
コンテスト
ユーザー vjudge1
提出日時 2026-01-11 14:22:44
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 227 ms / 2,000 ms
コード長 7,795 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,492 ms
コンパイル使用メモリ 363,372 KB
実行使用メモリ 27,524 KB
最終ジャッジ日時 2026-01-11 14:22:57
合計ジャッジ時間 11,458 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// - Author: Jorge_Slime - 11.01.2026 | 00:55:18
#include <bits/stdc++.h>
using namespace std; 
#define forn(i,a,b)  for(auto i{a};i<(b);++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) int((x).size())
#if defined(SLIME)
    #include "/home/jorge/slime_debug.hpp"   
#else                                        
    #define _(...) void(77)
#endif
using i64 = int64_t;         

struct Node{
    i64 sum;
    i64 lazyVal;
    bool haslazy;
};
class Lazy_SegTree{
public:
    #define left  node << 1
    #define right  node<< 1 | 1
    const i64 NEUTRO = 0; 
    std::vector<Node> tree;
    int size, logv = 0;
    Lazy_SegTree() : size(0), logv(0) {}
    Lazy_SegTree(int n){
        init(n);
    }
    void init(int n){
        logv = 0;
        size = n;
        while((1<<logv) < size) ++logv;
        size = 1<<logv;
        tree.assign(size << 1,{NEUTRO,0,false});
    }
    void modify(int node){
        tree[node].sum = op(tree[left].sum, tree[right].sum);
    }
    void init(const std::vector<i64> &ar) {
        int tam = (int)ar.size();
        for (int i = 0; i < tam; i++) {
            tree[size + i] = {ar[i],0,false};
        }
        for (int i = size - 1; i ; --i) {
            modify(i);
        }
    }
    void apply(int node, int l, int r, i64 val){
        tree[node].sum += val * (r - l + 1); // asignacin
        tree[node].lazyVal += val;
        tree[node].haslazy = true;
    }
    void propagate(int node, int l ,int r){
        if(tree[node].haslazy){
            int mid = (l + r) >> 1;
            apply(left, l, mid, tree[node].lazyVal);
            apply(right,  mid + 1, r, tree[node].lazyVal);
            tree[node].haslazy = false;
            tree[node].lazyVal = 0;
        }
    }
    void upd(int node,int nl,int nr,int ql,int qr,i64 val){
        if(nr < ql || nl > qr) return;
        if(ql <= nl && nr <= qr){
            apply(node,nl,nr,val);
            return;
        }
        propagate(node,nl,nr);
        int mid = (nl + nr) >> 1;
        upd(left, nl, mid, ql, qr, val);
        upd(right, mid + 1,nr, ql ,qr, val);
        modify(node);
    }
    void update(int l ,int r , i64 val){
        if(l>r) return;
        upd(1,0,size-1,l,r,val);
    }
    i64 queryRec(int node, int nl ,int nr, int ql, int qr){
        if(nr < ql || nl > qr) return NEUTRO;
        if(ql <= nl && nr <= qr){
            return tree[node].sum;
        }
        propagate(node, nl ,nr);
        int mid = (nl + nr)>>1;
        i64 iz = queryRec(left, nl , mid,ql,qr);
        i64 de = queryRec(right , mid + 1, nr, ql,qr);
        return op(iz,de);
    }
    i64 query(int l ,int r){
        if(l>r) return NEUTRO;
        return queryRec(1, 0 ,size-1,l,r);
    }
    static constexpr i64 op(i64 a, i64 b){
        return a + b; 
    }
    #undef left
    #undef right
};




template<bool P>//if edges weights  
struct HLD{
    int n, times;
    vector<vector<int>> G;
    vector<int> sz,in,head,fa,depth,heavy,rev_in;
    HLD(int n_){ init(n_); }
    void init(int n_){
        n = n_;times = 0;G.assign(n,{});
        fa.assign(n, -1); depth.assign(n, 0);
        head.assign(n, -1);in.assign(n, 0);
        sz.assign(n, 0);heavy.assign(n,-1);
        rev_in.assign(n,0);
    }
    void build(int root){
        dfsSz(root);
        dfsHLD(root, root);
    }
    void add_edge(int u, int v) {
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    // LCA utils
    bool is_ancestor(int a, int b) const {
        return in[a] <= in[b] && in[b] < in[a] + sz[a];
    }
    int lca(int u,int v){
        while(head[u] != head[v]){
            if(depth[head[u]] < depth[head[v]])
                std::swap(u,v);
            u = fa[head[u]];
        }
        return depth[u] < depth[v] ? u : v;
    }
    int dist(int u,int v){
        return depth[u] + depth[v] - 2 * depth[lca(u,v)];
    }
    int get_kth_ancestor(int a, int k){
        while (a != -1) {
            int h = head[a];
            if (in[a] - in[h] >= k)
                return rev_in[in[a] - k];
            k -= in[a] - in[h] + 1;
            a = fa[h];
        }
        return -1;
    }
    int get_kth_node_on_path(int a, int b, int k){
        int anc = lca(a, b); k--;
        int d1 = depth[a] - depth[anc];
        int d2 = depth[b] - depth[anc];
        if (k <= d1)
            return get_kth_ancestor(a, k);
        else
            return get_kth_ancestor(b, d1 + d2 - k);
    }
    // Update and Queries
    void updateNode(int node, i64 v, auto& seg) {
        seg.update(in[node],in[node],v);
    }
    i64 queryNode(int node,auto& seg){
        return seg.query(in[node],in[node]);
    }
    void updateSubtree(int node,i64 v, auto& seg){
        seg.update(in[node] + P,in[node] + sz[node] - 1,v);
    }
    i64 querySubtree(int node,auto& seg){
        return seg.query(in[node] + P,in[node] + sz[node] - 1);
    }
    void updatePath(int a,int b,i64 v, auto& seg){
        while (head[a] != head[b]) {
            if (depth[head[a]] > depth[head[b]]) {
                seg.update(in[head[a]], in[a],v);
                a = fa[head[a]];
            } else {
                seg.update(in[head[b]], in[b],v);
                b = fa[head[b]];
            }
        }
        if (depth[a] > depth[b]) std::swap(a, b);
        seg.update(in[a] + P, in[b], v);
    }
    i64 queryPath(int a, int b, auto& seg) {
        i64 ra = seg.NEUTRO, rb = seg.NEUTRO;
        while (head[a] != head[b]) {
            if (depth[head[a]] > depth[head[b]]) {
                ra = seg.op(ra, seg.query(in[head[a]], in[a]));
                a = fa[head[a]];
            } else {
                rb = seg.op(rb, seg.query(in[head[b]], in[b]));
                b = fa[head[b]];
            }
        }
        if (depth[a] > depth[b]) std::swap(a, b);
        return seg.op(ra,seg.op(seg.query(in[a] + P, in[b]),rb));
    }
    void initWeights(auto& e,auto& seg){
        forn(i, 0, n - 1){
            auto [u,v,w] = e[i];
            int nodo=(depth[u]>depth[v]?u:v);
            updateNode(nodo, w, seg);
        }
    }
private:
    void dfsSz(int node){
        sz[node] = 1; 
        int mx = 0; 
        for(auto& child : G[node]){
            if(child == fa[node]) continue; 
            fa[child] = node; 
            depth[child] = depth[node] + 1; 
            dfsSz(child); 
            sz[node] += sz[child]; 
            if(sz[child] > mx){
                mx = sz[child]; 
                heavy[node] = child; 
            }
        }
    }
    void dfsHLD(int node,int h){
        in[node] = times++; 
        head[node] = h; 
        rev_in[in[node]] = node; 
        if(heavy[node] != -1) dfsHLD(heavy[node], h);
        for(auto& child : G[node]){
            if(child == fa[node] || child == heavy[node]) continue; 
            dfsHLD(child , child);

        }
    }
};

struct EdgeNode{
    int u,v; 
    i64 w; 
};

auto solve([[maybe_unused]]auto&& tc)->void{ 
    int n; cin >> n; 
    vector<EdgeNode> edges(n - 1);
    Lazy_SegTree seg(n);
    HLD<1> hld(n); 
    forn(i,0,n - 1){
        int u,v; 
        i64 w; cin >> u >> v >>w;
        hld.add_edge(u, v);
        edges[i] = {u,v,w};
    }
    hld.build(0);
    hld.initWeights(edges,seg);
    int q; cin >> q; 
    forn(i, 0, q){
        int t; cin >> t; 
        if(t == 2){
            int b; cin >> b; 
            i64 ans = hld.queryPath(0,b,seg);
            cout << ans << '\n'; 
        }else{
            int a; 
            i64 x; cin >> a >> x; 
            hld.updateSubtree(a, x, seg);
        }
    }

};
[[gnu::target("avx2")]] auto main(void) -> int {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin.exceptions(ios::failbit | ios::badbit);
    size_t t_c = 1;
    //cin >> t_c;
    forn(t,0,t_c){ _(case(t)); solve(t); }
    _(time_());
    return 0;
} // I can....
0