結果

問題 No.900 aδδitivee
ユーザー kyort0nkyort0n
提出日時 2019-10-04 22:12:15
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,429 bytes
コンパイル時間 1,707 ms
コンパイル使用メモリ 185,048 KB
実行使用メモリ 36,552 KB
最終ジャッジ日時 2024-10-03 07:47:13
合計ジャッジ時間 6,163 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
12,496 KB
testcase_01 AC 4 ms
8,192 KB
testcase_02 AC 4 ms
8,192 KB
testcase_03 AC 4 ms
8,192 KB
testcase_04 AC 4 ms
8,192 KB
testcase_05 AC 4 ms
8,192 KB
testcase_06 AC 4 ms
8,064 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
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>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
//const ll mod = 1000000007;
typedef vector<vector<ll>> Graph;
template< typename G >
struct DoublingLowestCommonAncestor {
  const int LOG;
  vector< int > dep;
  const G &g;
  vector< vector< int > > table;

  DoublingLowestCommonAncestor(const G &g) : g(g), dep(g.size()), LOG(32 - __builtin_clz(g.size())) {
    table.assign(LOG, vector< int >(g.size(), -1));
  }

  void dfs(int idx, int par, int d) {
    table[0][idx] = par;
    dep[idx] = d;
    for(auto &to : g[idx]) {
      if(to != par) dfs(to, idx, d + 1);
    }
  }

  void build() {
    dfs(0, -1, 0);
    for(int k = 0; k + 1 < LOG; k++) {
      for(int i = 0; i < table[k].size(); i++) {
        if(table[k][i] == -1) table[k + 1][i] = -1;
        else table[k + 1][i] = table[k][table[k][i]];
      }
    }
  }

  int query(int u, int v) {
    if(dep[u] > dep[v]) swap(u, v);
    for(int i = LOG - 1; i >= 0; i--) {
      if(((dep[v] - dep[u]) >> i) & 1) v = table[i][v];
    }
    if(u == v) return u;
    for(int i = LOG - 1; i >= 0; i--) {
      if(table[i][u] != table[i][v]) {
        u = table[i][u];
        v = table[i][v];
      }
    }
    return table[0][u];
  }

  int P(int u, int d) {
    int digit = 0;
    while(d > 0) {
      if(d & (1 << digit)) {
        u = table[digit][u];
        d &= ~(1 << digit);
      }
      digit++;
    }
    return u;
  }
};

vector<int> pathes[100500];
vector<int> children[100500];
ll cost[100500], nowcost[100500];
void DFS(int now, ll nowval) {
  nowval += nowcost[now];
  cost[now] += nowval;
  nowcost[now] = 0;
  for(int &to : children[now]) DFS(to, nowval);
}

ll parent[100050];

void initialize(int now, int from) {
  for(auto to : pathes[now]) {
    if(to == from) continue;
    children[now].push_back(to);
    parent[to] = now;
    initialize(to, now);
  }
}

int ope, a, b;
ll x;
vector<l_l> query;
const int B = 2000;
ll u[100050], v[100050], w[100050];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    parent[0] = -1;
    Graph G(N);
    for(int i = 0; i <= N - 2; i++) {
        cin >> u[i] >> v[i] >> w[i];
        G[u[i]].push_back(v[i]);
        G[v[i]].push_back(u[i]);
        pathes[u[i]].push_back(v[i]);
        pathes[v[i]].push_back(u[i]);
    }
    initialize(0, -1);
    for(int i = 0; i <= N - 2; i++) {
        if(parent[u[i]] == v[i]) swap(u[i], v[i]);
        nowcost[v[i]] += w[i];
    }
    DFS(0, 0);
    DoublingLowestCommonAncestor<Graph> LCA(G);
    LCA.build();
    ll Q;
    cin >> Q;
    while(Q--) {
      cin >> ope;
      if(ope == 1) {
        cin >> a >> x;
        query.emplace_back(a, x);
        nowcost[a] += x;
      } else {
        cin >> b;
        ll ans = cost[b];
        for(l_l now : query) {
          if(LCA.query(now.first, b) == now.first) {
            ans += now.second * (LCA.dep[b] - LCA.dep[now.first]);
          }
        }
        cout << ans << "\n";
      }
      if((Q + 1) % B == 0) {
        query.clear();
        DFS(0, 0);
      }
    }
    return 0;
}
0