結果
| 問題 | No.900 aδδitivee |
| ユーザー |
 firiexp
|
| 提出日時 | 2019-10-04 21:47:58 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,939 bytes |
| コンパイル時間 | 822 ms |
| コンパイル使用メモリ | 94,708 KB |
| 最終ジャッジ日時 | 2024-11-14 21:42:51 |
| 合計ジャッジ時間 | 3,293 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
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@12/12.3.0/include/c++/12/vector:64,
from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/queue:61,
from main.cpp:6:
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1276: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>]'
1276 | push_back(const value_type& __x)
| ^~~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1276: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>&'}
1276 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1293: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>]'
1293 | push_back(value_type&& __x)
| ^~~~~~~~~
/home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_vector.h:1293:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<int, 3> >::value_type&&' {aka 'std::array<int, 3>&&'}
1293 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
main.cpp:200:19: error: no match for 'operator[]' (operand types are 'std::array<int, 3>' and 'int')
200 | if(G.dep[i[0]] > G.
ソースコード
#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;
}