結果

問題 No.900 aδδitivee
ユーザー yakamotoyakamoto
提出日時 2019-10-04 23:54:18
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 282 ms / 2,000 ms
コード長 3,560 bytes
コンパイル時間 1,941 ms
コンパイル使用メモリ 175,896 KB
実行使用メモリ 19,484 KB
最終ジャッジ日時 2024-04-14 12:19:51
合計ジャッジ時間 9,887 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 275 ms
15,284 KB
testcase_08 AC 278 ms
15,404 KB
testcase_09 AC 277 ms
15,412 KB
testcase_10 AC 274 ms
15,280 KB
testcase_11 AC 276 ms
15,288 KB
testcase_12 AC 274 ms
15,284 KB
testcase_13 AC 273 ms
15,284 KB
testcase_14 AC 282 ms
15,284 KB
testcase_15 AC 273 ms
15,284 KB
testcase_16 AC 275 ms
15,280 KB
testcase_17 AC 273 ms
15,412 KB
testcase_18 AC 277 ms
15,284 KB
testcase_19 AC 269 ms
15,540 KB
testcase_20 AC 272 ms
15,408 KB
testcase_21 AC 277 ms
15,412 KB
testcase_22 AC 266 ms
19,484 KB
testcase_23 AC 269 ms
19,484 KB
testcase_24 AC 270 ms
19,356 KB
testcase_25 AC 266 ms
19,356 KB
testcase_26 AC 265 ms
19,356 KB
testcase_27 AC 266 ms
19,484 KB
testcase_28 AC 268 ms
19,360 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#ifndef SOLUTION_COMMON_H

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using PI = pair<int, int>;
template<class T> using V = vector<T>;
using VI = V<int>;
#define _1 first
#define _2 second

#ifdef MY_DEBUG
# define DEBUG(x) x
#else
# define DEBUG(x)
#endif

template<class T>
inline void debug(T &A) {
  DEBUG(
      for (const auto &a : A) {
        cerr << a << " ";
      }
      cerr << '\n';
  )
}

template<class T, class Func>
inline void debug_with_format(T &A, Func f) {
  DEBUG(
      for (const auto &a : A) {
        cerr << f(a) << " ";
      }
      cerr << '\n';
  )
}

template<class T>
inline void debug_dim2(T &A) {
  DEBUG(
      for (const auto &as : A) {
        debug(as);
      }
  )
}

template<typename ... Args>
inline void debug(const char *format, Args const &... args) {
  DEBUG(
      fprintf(stderr, format, args ...);
      cerr << '\n';
  )
}

template<typename ... Args>
string format(const string &fmt, Args ... args) {
  size_t len = snprintf(nullptr, 0, fmt.c_str(), args ...);
  vector<char> buf(len + 1);
  snprintf(&buf[0], len + 1, fmt.c_str(), args ...);
  return string(&buf[0], &buf[0] + len);
}

template<class T1, class T2>
string fmtP(pair<T1, T2> a) {
  stringstream ss;
  ss << "(" << a._1 << "," << a._2 << ")";
  return ss.str();
}

#define SOLUTION_COMMON_H

#endif //SOLUTION_COMMON_H


class BIT {
public:
  int N;
  V<ll> bit;
  BIT(int n): N(n + 1), bit(N) {}

  void add(int i, ll x) {
    i++;
    while(i < N) {
      bit[i] += x;
      i += i & -i;
    }
  }

  ll query(int i) {
    ll ans = 0ll;
    while(i) {
      ans += bit[i];
      i -= i & -i;
    }
    return ans;
  }
};

const int MOD = 1000000007;

class D {
public:
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    V<V<PI>> g(n);
    for (int i = 0; i < n - 1; ++i) {
      int u, v, w;
      in >> u >> v >> w;
      g[u].emplace_back(v, w);
      g[v].emplace_back(u, w);
    }
    V<ll> dp(n);
    VI tour;
    V<PI> pos(n);
    VI depth(n);
    int mx_depth = 0;
    function<void(int, int, int)> init = [&](int v, int p, int weight) {
      pos[v]._1 = (int)tour.size();
      tour.push_back(v);
      if (p != -1) {
        dp[v] = dp[p] + weight;
        depth[v] = depth[p] + 1;
        mx_depth = max(mx_depth, depth[v]);
      }
      for (const auto &e : g[v]) {
        if (e._1 != p) init(e._1, v, e._2);
      }
      pos[v]._2 = (int)tour.size();
      tour.push_back(v);
    };
    init(0, -1, 0);

    debug(depth);
    debug("%d", mx_depth);
//    debug(tour);
//    DEBUG(
//    for (int i = 0; i < n; ++i) {
//      cerr << "(" << pos[i]._1 << "," << pos[i]._2 << ") ";
//    }
//    )

    BIT bit(2 * n);
    BIT cum(2 * n);
    int q;
    in >> q;
    for (int i = 0; i < q; ++i) {
      int tpe;
      in >> tpe;
      if (tpe == 1) {
        int a, x;
        in >> a >> x;
        bit.add(pos[a]._1, x);
        bit.add(pos[a]._2, -x);
        cum.add(pos[a]._1, ((ll)(mx_depth - depth[a])) * x);
        cum.add(pos[a]._2, -((ll)(mx_depth - depth[a])) * x);
      } else {
        int b;
        in >> b;
        debug("%d %d", b, pos[b]._1);
        ll v = cum.query(pos[b]._1) - bit.query(pos[b]._1) * (mx_depth - depth[b]) + dp[b];
        out << v << '\n';
      }
    }
  }
};


int main() {
	D solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}
0