結果

問題 No.900 aδδitivee
ユーザー tonegawatonegawa
提出日時 2020-02-06 23:45:00
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 487 ms / 2,000 ms
コード長 5,376 bytes
コンパイル時間 1,964 ms
コンパイル使用メモリ 121,336 KB
実行使用メモリ 80,732 KB
最終ジャッジ日時 2024-09-25 07:00:09
合計ジャッジ時間 14,269 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,400 KB
testcase_01 AC 4 ms
6,400 KB
testcase_02 AC 4 ms
6,528 KB
testcase_03 AC 5 ms
6,656 KB
testcase_04 AC 4 ms
6,528 KB
testcase_05 AC 5 ms
6,400 KB
testcase_06 AC 5 ms
6,528 KB
testcase_07 AC 460 ms
78,948 KB
testcase_08 AC 465 ms
79,008 KB
testcase_09 AC 455 ms
79,040 KB
testcase_10 AC 449 ms
79,008 KB
testcase_11 AC 471 ms
79,012 KB
testcase_12 AC 479 ms
79,008 KB
testcase_13 AC 487 ms
79,004 KB
testcase_14 AC 480 ms
79,276 KB
testcase_15 AC 477 ms
79,072 KB
testcase_16 AC 476 ms
79,140 KB
testcase_17 AC 471 ms
79,012 KB
testcase_18 AC 472 ms
79,012 KB
testcase_19 AC 472 ms
79,068 KB
testcase_20 AC 475 ms
79,008 KB
testcase_21 AC 473 ms
79,008 KB
testcase_22 AC 421 ms
80,596 KB
testcase_23 AC 418 ms
80,688 KB
testcase_24 AC 415 ms
80,660 KB
testcase_25 AC 414 ms
80,732 KB
testcase_26 AC 415 ms
80,668 KB
testcase_27 AC 419 ms
80,668 KB
testcase_28 AC 419 ms
80,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvv vector<vvl>
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvvl(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
typedef __int128_t lll;
using namespace std;



struct segtree{
  ll M=1, INIT;
  vector<ll> dat;
  segtree(){};
  segtree(ll N, ll num){
    INIT = num;
    while(M<N) M*=2;
    for(int i=0;i<M*2-1;i++)  dat.push_back(num);
  }
  void update(ll x, ll k, ll l=0, int r=-1){
    if(r==-1) r = M;
    k+=M-1;
    dat[k] += x;
    while(k>0) k = (k-1)/2, dat[k] = dat[k*2+1] + dat[k*2+2];
  }
  ll query(ll a, ll b=-1, ll k=0, ll l=0, ll r=-1){
    if(r==-1) r = M;
    if(b==-1) b = M;
    if(r<=a || b<=l) return INIT;
    if(a<=l && r<=b) return dat[k];
    ll A = query(a, b, k*2+1, l, (l+r)/2);
    ll B = query(a, b, k*2+2, (l+r)/2, r);
    return A + B;
  }
};
struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;
    segtree sg;
public:
  LazySegmentTree(){};
  LazySegmentTree(vector<ll> v, segtree s) {
    sg = s;
    int sz = (int)v.size();
    n = 1; while(n < sz) n *= 2;
    node.resize(2*n-1);
    lazy.resize(2*n-1, 0);
    for(int i=0; i<sz; i++) node[i+n-1] = v[i];
    for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
  }
  void eval(int k, int l, int r) {
    if(lazy[k] != 0) {
      node[k] += (lazy[k]*sg.dat[k]);
      //std::cout << lazy[k] << " " << sg.dat[k] << " " << k<< '\n';
      if(r - l > 1) {
        lazy[2*k+1] += lazy[k];
        lazy[2*k+2] += lazy[k];
      }
      lazy[k] = 0;
    }
  }
  void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
    if(r < 0) r = n;
    eval(k, l, r);
    if(b <= l || r <= a) return;
    if(a <= l && r <= b) {
      lazy[k] += x;
      eval(k, l, r);
    }
    else {
      add(a, b, x, 2*k+1, l, (l+r)/2);
      add(a, b, x, 2*k+2, (l+r)/2, r);
      node[k] = node[2*k+1] + node[2*k+2];
    }
  }
  ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
    if(r < 0) r = n;
    eval(k, l, r);
    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return node[k];
    ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
    ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
    return vl + vr;
  }
};
struct EulerTour{
  ll N, root = 0, o = 0;
  vector<vector<ll>> G;
  LazySegmentTree seg;
  segtree table;
  vll begin, end, tour, depth;
  vvl parent;
  EulerTour(vector<vector<ll>> g){
    N = g.size();
    G = g;
    begin.resize(N+1);
    end.resize(N+1);
    depth.resize(N+1);
    parent.resize(30, vll(N+1));
    table = segtree(2*N+1, 0);
    init_();
    seg = LazySegmentTree(vll(2*N+1, 0), table);
  }
  void init_(){
    tour_init(root, -1);
    lca_init();
    table_init();
  }
  void tour_init(ll now, ll from){
    begin[now] = o;
    tour.push_back(now);
    o++;
    for(int i=0;i<G[now].size();i++){
      if(G[now][i]==from) continue;
      tour_init(G[now][i], now);
      tour.push_back(now);
      o++;
    }
    end[now] = o;
  }
  void lca_init(){
    dfs(root, -1, 0);
    for(int k=0;k+1<30;k++){
      for(int v=0;v<N+1;v++){
        if(parent[k][v]<0) parent[k+1][v] = -1;
        else parent[k+1][v] = parent[k][parent[k][v]];
      }
    }
  }
  void table_init(){
    for(int i=0;i<tour.size()-1;i++){
      if(depth[tour[i]]>depth[tour[i+1]]) table.update(-1, i);
      else table.update(1, i);
    }
  }
  void dfs(int v, int p, int d){
    parent[0][v] = p, depth[v] = d;
    for(int i=0;i<G[v].size();i++) if(G[v][i] != p) dfs(G[v][i], v, d+1);
  }
  int lca(int u, int v){
    if(depth[u]>depth[v]) swap(u, v);
    for(int k=0;k<30;k++)if((depth[v]-depth[u])>>k & 1) v = parent[k][v];
    if(u==v) return u;
    for(int k=30-1;k>=0;k--){
      if(parent[k][u] != parent[k][v]){
        u = parent[k][u];
        v = parent[k][v];
      }
    }
    return parent[0][u];
  }

  // aの部分木の各辺にx加算
  // パスa,bの値取得
  void update(ll a, ll x){
    //std::cout << "UPDATE" << begin[a] << " " << end[a]-1 << '\n';
    seg.add(begin[a], end[a]-1, x);
  }
  ll query(ll a, ll b){
    ll l = lca(a, b);
    ll A = seg.getsum(begin[root], begin[a]);
    ll B = seg.getsum(begin[root], begin[b]);
    ll C = seg.getsum(begin[root], begin[l]);
    return A + B - 2*C;
  }
};
struct edge{ll to, cost;};
vll d(100001, 0);
vector<vector<edge>> T(100001);
void DFS(ll now, ll from, ll c){
  d[now] = c;
  for(int i=0;i<T[now].size();i++){
    if(T[now][i].to==from) continue;
    DFS(T[now][i].to, now, c+T[now][i].cost);
  }
}
int main(int argc, char const *argv[]) {
  ll a, b, c, n;std::cin >> n;
  vvl G = vv(n, 0, 0, ll);
  re(i, n-1){
    std::cin >> a >> b >> c;
    G[a].push_back(b);
    G[b].push_back(a);
    T[a].push_back(edge{b, c});
    T[b].push_back(edge{a, c});
  }
  DFS(0, -1, 0);
  EulerTour e(G);
  ll q;std::cin >> q;
  re(i, q){
    std::cin >> a >> b;
    if(a==1) {
      std::cin >> c;
      e.update(b, c);
    }else std::cout << e.query(0, b) + d[b] << '\n';
  }
  return 0;
}
0