結果

問題 No.900 aδδitivee
ユーザー たこしたこし
提出日時 2019-10-04 22:56:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 378 ms / 2,000 ms
コード長 4,424 bytes
コンパイル時間 2,514 ms
コンパイル使用メモリ 205,352 KB
実行使用メモリ 32,984 KB
最終ジャッジ日時 2024-04-14 11:28:02
合計ジャッジ時間 12,666 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
23,340 KB
testcase_01 AC 13 ms
23,544 KB
testcase_02 AC 13 ms
23,056 KB
testcase_03 AC 13 ms
23,364 KB
testcase_04 AC 13 ms
23,216 KB
testcase_05 AC 13 ms
23,952 KB
testcase_06 AC 13 ms
23,436 KB
testcase_07 AC 374 ms
27,600 KB
testcase_08 AC 375 ms
27,816 KB
testcase_09 AC 372 ms
27,612 KB
testcase_10 AC 373 ms
27,636 KB
testcase_11 AC 372 ms
27,548 KB
testcase_12 AC 375 ms
27,680 KB
testcase_13 AC 373 ms
27,640 KB
testcase_14 AC 370 ms
27,616 KB
testcase_15 AC 375 ms
27,632 KB
testcase_16 AC 372 ms
27,644 KB
testcase_17 AC 375 ms
27,672 KB
testcase_18 AC 378 ms
27,644 KB
testcase_19 AC 374 ms
27,820 KB
testcase_20 AC 377 ms
27,628 KB
testcase_21 AC 374 ms
27,592 KB
testcase_22 AC 349 ms
32,836 KB
testcase_23 AC 351 ms
32,872 KB
testcase_24 AC 347 ms
32,984 KB
testcase_25 AC 351 ms
32,912 KB
testcase_26 AC 349 ms
32,956 KB
testcase_27 AC 351 ms
32,728 KB
testcase_28 AC 350 ms
32,824 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define INF 100000000
#define YJ 1145141919
#define INF_INT_MAX 2147483647
#define INF_LL 9223372036854775
#define INF_LL_MAX 9223372036854775807
#define EPS 1e-10
#define MOD 1000000007
#define MOD9 998244353
#define Pi acos(-1)
#define LL long long
#define ULL unsigned long long
#define LD long double

#define int long long

using II = pair<int, int>;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(a)  begin((a)), end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())

class RangeNode {
public:
  RangeNode() {
    init();
  }

  void init() {
    delay = delayFlag = 0;
    val = 0;
  }

  //クエリ処理
  static int evaluateQuery(int p1, int p2) 
  {
    return p1 + p2;
  }

  //range処理
  void evaluateRange() 
  {
    val += delay * rangeSum;
  }

  //delay処理
  void evaluateDelay(int d)
  {
    delay += d;
  }

  //単位元(クエリ処理)
  static int unit()
  {
    return 0;
  }

  int val;
  int delay;
  bool delayFlag;
  int rangeSum = 0;

};

template<class T, int Size>
class RangeSegmentTree {
public:
  RangeSegmentTree() 
  {
    init();
  }

  void init()
  {
    n = 1;
    while(n < Size) n *= 2;
    node.clear(); node.resize(2*n);
  }

  void setRangeSum()
  {
    for(int p = 2*n-1; 0 <= p; p--) {
      // cerr << p << " " << node[p].rangeSum << endl;
      if(p == 0) break;
      node[(p-1)/2].rangeSum += node[p].rangeSum;
    }
  }

  void evaluateRangeNode(int k, int l, int r)
  {
    if(node[k].delayFlag) {
      node[k].evaluateRange();
      if(r-l>1) {
        node[2*k+1].evaluateDelay(node[k].delay);
        node[2*k+2].evaluateDelay(node[k].delay);
        node[2*k+1].delayFlag = node[2*k+2].delayFlag = true;
      }
      node[k].delayFlag = false;
      node[k].delay = 0;
    }
  }

  void updateRange(int l, int r, int v)
  {
    _updateRange(l,r,v,0,0,n);
  }

  int query(int l, int r)
  {
    return _query(l,r,0,0,n);
  }

  vector<T> node;
  int n;

  void _updateRange(int l, int r, int v, int k, int a, int b)
  {
    evaluateRangeNode(k,a,b);

    if(b <= l || r <= a) return;
    else if(l <= a && b <= r) {
      node[k].evaluateDelay(v);
      node[k].delayFlag = true;
      evaluateRangeNode(k,a,b);
      return;
    } else {
      int mid = (a+b)/2;
      _updateRange(l,r,v,2*k+1,a,mid);
      _updateRange(l,r,v,2*k+2,mid,b);
      node[k].val = RangeNode::evaluateQuery(node[2*k+1].val, node[2*k+2].val);
      return;
    }
  }

  int _query(int l, int r, int k, int a, int b)
  {
    evaluateRangeNode(k,a,b);
    
    if(b <= l || r <= a) return RangeNode::unit();
    else if(l <= a && b <= r) {
      return node[k].val;
    } else {
      int mid = (a+b)/2;
      int vl = _query(l,r,2*k+1,a,mid);
      int vr = _query(l,r,2*k+2,mid,b);
      return RangeNode::evaluateQuery(vl,vr);
    }
  }
};

const int MAX_N = 100005;
int N;
vector<II> Edge[MAX_N];

RangeSegmentTree<RangeNode, 2*MAX_N> rgt;

int INDEX[2*MAX_N];
int first[MAX_N], last[MAX_N];

void setRangeSegmentTree(int pos, int& index)
{
  first[pos] = index;
  for(II edge : Edge[pos]) {

    rgt.node[rgt.n-1 + index].rangeSum = 1;
    INDEX[index++] = pos;

    setRangeSegmentTree(edge.first, index);
  }

  if(pos != 0)
  rgt.node[rgt.n-1 + index].rangeSum = -1;
  last[pos] = index;
  INDEX[index++] = pos;
}

void setWeight(int pos, int& index) 
{
  for(II edge : Edge[pos]) {
    int next = edge.first;
    int w = edge.second;

    rgt.updateRange(index, index+1, w);

    index++;
    setWeight(next, index);

    rgt.updateRange(index-1, index, w);
  }
  index++;
}

signed main()
{
  cin >> N;
  REP(n,N-1) {
    int u, v, w; cin >> u >> v >> w;
    Edge[u].push_back(II(v,w));
  }

  rgt.init();

  int index = 0;
  setRangeSegmentTree(0, index);
  rgt.setRangeSum();
  index = 0;
  setWeight(0, index);

  int Q; cin >> Q;
  REP(q,Q) {
    int a; cin >> a;
    if(a == 1) {
      int b, c; cin >> b >> c;
      rgt.updateRange(first[b], last[b], c);
    } else {
      int b; cin >> b;
      cout << rgt.query(0,first[b]) << endl;
    }
  }

  return 0;
}
0