結果

問題 No.900 aδδitivee
ユーザー tonegawatonegawa
提出日時 2020-02-06 23:20:50
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,416 bytes
コンパイル時間 1,797 ms
コンパイル使用メモリ 123,040 KB
実行使用メモリ 80,832 KB
最終ジャッジ日時 2024-09-25 06:57:50
合計ジャッジ時間 14,020 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,400 KB
testcase_01 AC 4 ms
6,400 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 <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]);
            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){
    seg.add(begin[a], end[a], 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