結果

問題 No.900 aδδitivee
ユーザー firiexpfiriexp
提出日時 2019-10-04 21:47:58
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,939 bytes
コンパイル時間 1,243 ms
コンパイル使用メモリ 94,608 KB
最終ジャッジ日時 2024-04-14 10:28:50
合計ジャッジ時間 2,773 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:14:13: error: 'uint32_t' does not name a type
   14 | using u32 = uint32_t;
      |             ^~~~~~~~
main.cpp:11:1: note: 'uint32_t' is defined in header '<cstdint>'; did you forget to '#include <cstdint>'?
   10 | #include <cmath>
  +++ |+#include <cstdint>
   11 | 
main.cpp: In function 'int main()':
main.cpp:195:20: error: no matching function for call to 'std::vector<std::array<int, 3> >::push_back(<brace-enclosed initializer list>)'
  195 |         A.push_back({u, v, w});
      |         ~~~~~~~~~~~^~~~~~~~~~~
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/vector:66,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/queue:63,
                 from main.cpp:6:
/home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/stl_vector.h:1278:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<int, 3>; _Alloc = std::allocator<std::array<int, 3> >; value_type = std::array<int, 3>]'
 1278 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/stl_vector.h:1278:35: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const std::vector<std::array<int, 3> >::value_type&' {aka 'const std::array<int, 3>&'}
 1278 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/stl_vector.h:1295:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::array<int, 3>; _Alloc = std::allocator<std::array<int, 3> >; value_type = std::array<int, 3>]'
 1295 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc/13.2.0/include/c++/13/bits/stl_vector.h:1295:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<int, 3> >:

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

class HeavyLightDecomposition {
    void dfs_sz(int v){
        for (auto &&u : G[v]) {
            if(u == par[v]) continue;
            par[u] = v;
            dep[u] = dep[v] + 1;
            dfs_sz(u);
            sub_size[v] += sub_size[u];
            if(sub_size[u] > sub_size[G[v][0]]) swap(u, G[v][0]);
        }
    }

    void dfs_hld(int v, int c, int &pos){
        id[v] = pos++;
        id_inv[id[v]]= v;
        tree_id[v] = c;
        for (auto &&u : G[v]) {
            if(u == par[v]) continue;
            head[u] = (u == G[v][0] ? head[v] : u);
            dfs_hld(u, c, pos);
        }
    }

public:
    int n;
    vector<vector<int>> G;
    vector<int> par, dep, sub_size, id, id_inv, tree_id, head;
    explicit HeavyLightDecomposition(int n) : n(n), G(n), par(n), dep(n), sub_size(n, 1),
                                              id(n), id_inv(n), tree_id(n), head(n){}
    explicit HeavyLightDecomposition(vector<vector<int>> &G) :
            G(G), n(n), par(n), dep(n) , sub_size(n, 1), id(n), id_inv(n), tree_id(n), head(n) {}

    void add_edge(int u, int v){
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    void build(vector<int> roots = {0}){
        int c = 0, pos = 0;
        for (auto &&i : roots) {
            dfs_sz(i);
            head[i] = i;
            dfs_hld(i, c++, pos);
        }
    }

    int lca(int u, int v){
        while(true){
            if(id[u] > id[v]) swap(u, v);
            if(head[u] == head[v]) return u;
            v = par[head[v]];
        }
    }

    int distance(int u, int v){
        return dep[u] + dep[v] - 2*dep[lca(u, v)];
    }


    template<typename F>
    void query(int u, int v, const F &f){
        while(true){
            if(id[u] > id[v]) swap(u, v);
            f(max(id[head[v]], id[u]), id[v]+1);
            if(head[u] == head[v]) break;
            v = par[head[v]];
        }
    }

    template<typename F>
    void query_edge(int u, int v, const F &f){
        while(true){
            if(id[u] > id[v]) swap(u, v);
            if(head[u] != head[v]) {
                f(id[head[v]], id[v]+1);
                v = par[head[v]];
            }else {
                if(u != v) f(id[u]+1, id[v]+1);
                break;
            }
        }
    }

    template<typename T, typename Q, typename F>
    T query(int u, int v, const T &e, const Q &q, const F &f){
        T l = e, r = e;
        while(true){
            if(id[u] > id[v]) swap(u, v), swap(l, r);
            l = f(l, q(max(id[head[v]], id[u]), id[v]+1));
            if(head[u] != head[v]) v = par[head[v]];
            else break;
        }
        return f(l, r);
    }

};

template <class M>
struct LazySegmentTree{
    using T = typename M::T;
    using L = typename M::L;
    int sz, height{};
    vector<T> seg; vector<L> lazy;
    explicit LazySegmentTree(int n) {
        sz = 1;
        while(sz < n) sz <<= 1, height++;
        seg.assign(2*sz, M::e());
        lazy.assign(2*sz, M::l());
    }

    void set(int k, const T &x){
        seg[k + sz] = x;
    }

    void build(){
        for (int i = sz-1; i > 0; --i) seg[i] = M::f(seg[2*i], seg[2*i+1]);
    }

    T reflect(int k){ return lazy[k] == M::l() ? seg[k] : M::g(seg[k], lazy[k]); }

    void eval(int k){
        if(lazy[k] == M::l()) return;
        lazy[(k<<1)|0] = M::h(lazy[(k<<1)|0], lazy[k]);
        lazy[(k<<1)|1] = M::h(lazy[(k<<1)|1], lazy[k]);
        seg[k] = reflect(k);
        lazy[k] = M::l();
    }
    void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
    void recalc(int k) { while(k >>= 1) seg[k] = M::f(reflect((k<<1)|0), reflect((k<<1)|1));}
    void update(int a, int b, const L &x){
        thrust(a += sz); thrust(b += sz-1);
        for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
            if(l&1) lazy[l] = M::h(lazy[l], x), l++;
            if(r&1) --r, lazy[r] = M::h(lazy[r], x);
        }
        recalc(a);
        recalc(b);
    }

    T query(int a, int b){ // [l, r)
        thrust(a += sz);
        thrust(b += sz-1);
        T ll = M::e(), rr = M::e();
        for(int l = a, r = b+1; l < r; l >>=1, r>>=1) {
            if (l & 1) ll = M::f(ll, reflect(l++));
            if (r & 1) rr = M::f(reflect(--r), rr);
        }
        return M::f(ll, rr);
    }

    T operator[](const int &k) const { // 0-indexed
        return seg[k + sz];
    }
};

struct Monoid{
    using T = pair<ll, int>;
    using L = ll;
    static T f(T a, T b) { return {a.first+b.first, a.second+b.second}; }
    static T g(T a, L b) {
        return {a.first+b*a.second, a.second};
    }
    static L h(L a, L b) {
        return a+b;
    }
    static T e() { return {0, 0}; }
    static L l() { return 0; }
};

int main() {
    int n;
    cin >> n;
    HeavyLightDecomposition G(n);
    vector<array<int, 3>> A;
    for (int i = 0; i < n - 1; ++i) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        G.add_edge(u, v);
        A.push_back({u, v, w});
    }
    G.build();
    LazySegmentTree<Monoid> seg(n);
    for (auto &&i : A) {
        if(G.dep[i[0]] > G.dep[i[1]]) swap(i[0], i[1]);
        seg.set(G.id[i[1]], {i[2], 1});
    }
    seg.build();
    int q;
    cin >> q;
    for (int j = 0; j < q; ++j) {
        int no; scanf("%d", &no);
        if(no == 1){
            int a, x;
            scanf("%d %d", &a, &x);
            seg.update(G.id[a]+1, G.id[a]+G.sub_size[a], x);
        }else {
            int a;
            scanf("%d", &a);
            ll ans = 0;
            auto f = [&](int s, int t){ ans += seg.query(s, t).first; };
            G.query_edge(0, a, f);
            printf("%lld\n", ans);
        }
    }
    return 0;
}
0