結果

問題 No.900 aδδitivee
ユーザー kanra824kanra824
提出日時 2019-10-05 00:15:01
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,666 bytes
コンパイル時間 2,035 ms
コンパイル使用メモリ 186,140 KB
実行使用メモリ 55,552 KB
最終ジャッジ日時 2024-10-03 09:58:39
合計ジャッジ時間 13,952 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
template<typename T>
struct Edge {
    int from, to;
    T cost;
    Edge(int from, int to, T cost) {
        this->from = from;
        this->to = to;
        this->cost = cost;
    }
};
bool operator == (Edge<int> e1, Edge<int> e2) {
    return e1.from == e2.from &&
            e1.to == e2.to &&
            e1.cost == e2.cost;
}
template<typename T>
using Edges = std::vector<Edge<T>>;
template<typename T>
using Graph = std::vector<Edges<T>>;
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
class LazySegmentTree
{
    int n;
    using T1 = ll;
    using T2 = ll;
    void eval(int k, int l, int r)
    {
        if (lazy[k] == 0)
            return;
        node[k] = node[k] + lazy[k];
        if (r - l > 1)
        {
            lazy[2 * k + 1] = lazy[2 * k + 1] + lazy[k] / 2;
            lazy[2 * k + 2] = lazy[2 * k + 2] + lazy[k] / 2;
        }
        lazy[k] = 0;
    }
  public:
    std::vector<T1> node;
    std::vector<T2> lazy;
    LazySegmentTree(int _n)
    {
        int sz = _n;
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1, 0);
        lazy.resize(2 * n - 1, 0);
    }
    LazySegmentTree(int _n, T1 _v)
    {
        int sz = _n;
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1, 0);
        lazy.resize(2 * n - 1, 0);
        for (int i = 0; i < sz; i++)
            node[i + n - 1] = _v;
        for (int i = n - 2; i >= 0; i--)
            node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }
    void update(int a, int b, T2 val, int l = 0, int r = -1, int k = 0)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
            return;
        if (a <= l && r <= b)
        {
            lazy[k] = lazy[k] + (r - l) * val;
            eval(k, l, r);
        }
        else
        {
            int mid = (l + r) / 2;
            update(a, b, val, l, mid, 2 * k + 1);
            update(a, b, val, mid, r, 2 * k + 2);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }
    T1 query(int a, int b, int l = 0, int r = -1, int k = 0)
    {
        if (r < 0)
            r = n;
        eval(k, l, r);
        if (b <= l || r <= a)
            return 0;
        if (a <= l && r <= b)
            return node[k];
        int mid = (l + r) / 2;
        T1 vl = query(a, b, l, mid, 2 * k + 1);
        T1 vr = query(a, b, mid, r, 2 * k + 2);
        return vl + vr;
    }
};
map<int, int> pl, mi;
void dfs(int now, const Graph<ll> &g, vector<ll> &dist, vector<ll> &depth, int &idx, int &plusidx, int &minusidx, vector<int> &plus, vector<int> &plused, vector<int> &minus, vector<int> &minusbeg) {
  int sz = g[now].size();
  for(int i=0;i<sz;++i) {
    int next = g[now][i].to;
    ll cost = g[now][i].cost;
    dist[next] = dist[now] + cost;
    depth[next] = depth[now] + 1;
    plus[next] = idx++;
    plusidx++;
    pl[idx] = plusidx;
    mi[idx] = minusidx;
    minusbeg[next] = minusidx;
    dfs(next, g, dist, depth, idx, plusidx, minusidx, plus, plused, minus, minusbeg);
    plused[next] = plusidx;
    minus[next] = idx++;
    minusidx++;
    pl[idx] = plusidx;
    mi[idx] = minusidx;
  }
}
int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  Graph<ll> g(n);
  for(int i=0;i<n-1;++i) {
    int u, v; ll w; cin >> u >> v >> w;
    g[u].push_back(Edge<ll>(u, v, w));
  }
  vector<ll> dist(n);
  vector<ll> depth(n);
  vector<int> plus(n);
  vector<int> plused(n);
  vector<int> minus(n);
  vector<int> minusbeg(n);
  dist[0] = 0;
  depth[0] = 0;
  int idx = 0, plusidx = 0, minusidx = 0;
  dfs(0, g, dist, depth, idx, plusidx, minusidx, plus, plused, minus, minusbeg);
  LazySegmentTree lst1(idx), lst2(idx);
  ll add0 = 0;
  int q; cin >> q;
  while(q > 0) {
    q--;
    int t; cin >> t;
    if(t == 1) {
      int a; ll x; cin >> a >> x;
      if(a == 0) {
        add0 += x;
        continue;
      }
      lst1.update(pl[plus[a]]+1, plused[a], x);
      lst2.update(minusbeg[a], mi[minus[a]], -x);
    } else {
      int b; cin >> b;
      ll ans = dist[b] + add0 * depth[b];
      ans += lst1.query(0, pl[plus[b]]+1);
      ans += lst2.query(0, mi[minus[b]]);
      cout << ans << endl;
    }
  }
}
0