結果
問題 | No.1637 Easy Tree Query |
ユーザー |
|
提出日時 | 2021-08-06 22:08:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 244 ms / 2,000 ms |
コード長 | 1,165 bytes |
コンパイル時間 | 889 ms |
コンパイル使用メモリ | 104,816 KB |
実行使用メモリ | 13,548 KB |
最終ジャッジ日時 | 2024-09-17 03:52:24 |
合計ジャッジ時間 | 7,619 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <iomanip> #include <cmath> #include <stdio.h> #include <queue> #include <deque> #include <cstdio> #include <set> #include <map> #include <bitset> #include <stack> #include <cctype> using namespace std; vector<vector<int>> vec(200020); vector<pair<int,int>> v; int co[200020] = {}; long long sum[200020] = {}; bool bo[200020] = { false }; int main() { long long n, q; cin >> n >> q; for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; vec[a].emplace_back(b); vec[b].emplace_back(a); co[a]++, co[b]++; sum[i] = 1; } sum[n] = 1; bo[1] = true; queue<int> que; que.push(1); while (!que.empty()) { int x = que.front(); que.pop(); for (int i = 0; i < vec[x].size(); i++) { if (!bo[vec[x][i]]) { bo[vec[x][i]] = true; que.push(vec[x][i]); v.emplace_back(make_pair(vec[x][i], x)); } } } reverse(v.begin(), v.end()); for (int i = 0; i < v.size(); i++) { sum[v[i].second] += sum[v[i].first]; } long long ans = 0; for (int i = 0; i < q; i++) { int p; long long x; cin >> p >> x; ans += sum[p] * x; cout << ans << endl; } }