結果
問題 | No.1637 Easy Tree Query |
ユーザー |
![]() |
提出日時 | 2021-07-07 17:48:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 298 ms / 2,000 ms |
コード長 | 1,050 bytes |
コンパイル時間 | 1,750 ms |
コンパイル使用メモリ | 175,056 KB |
実行使用メモリ | 17,664 KB |
最終ジャッジ日時 | 2024-09-17 03:18:25 |
合計ジャッジ時間 | 9,713 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct Edge { int u; int v; int cost; Edge(int a, int b, int c) : u(a), v(b), cost(c) { } }; using Graph = vector<vector<Edge>>; vector<int> depth; vector<long long> subtree_size; void dfs(const Graph& G, int v, int p, int d) { depth[v] = d; for (auto nv : G[v]) { if (nv.v == p) continue; dfs(G, nv.v, v, d + 1); } subtree_size[v] = 1; for (auto c : G[v]) { if (c.v == p) continue; subtree_size[v] += subtree_size[c.v]; } } int main() { long long N, Q; cin >> N >> Q; Graph G(N); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; G[a - 1].emplace_back(a - 1, b - 1, 1); G[b - 1].emplace_back(b - 1, a - 1, 1); } depth.assign(N, 0); subtree_size.assign(N, 0); dfs(G, 0, -1, 0); long long ans = 0; for (int i = 0; i < Q; i++) { long long p, x; cin >> p >> x; ans += subtree_size[p - 1] * x; cout << ans << endl; } }