結果
問題 | No.1637 Easy Tree Query |
ユーザー |
![]() |
提出日時 | 2021-08-08 20:43:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 286 ms / 2,000 ms |
コード長 | 719 bytes |
コンパイル時間 | 1,902 ms |
コンパイル使用メモリ | 197,924 KB |
最終ジャッジ日時 | 2025-01-23 17:07:40 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;void dfs(vector<vector<int>> &G, vector<ll> &dp, int v) {ll now = 1;dp[v] = 1;for (int i = 0; i < G[v].size(); i++) {if (dp[G[v][i]] == -1) {dfs(G, dp, G[v][i]);now += dp[G[v][i]];}}dp[v] = now;return;}int main() {int n, q;cin >> n >> q;vector<vector<int>> G(n);for (int i = 0; i < n - 1; i++) {int a, b;cin >> a >> b;a--;b--;G[a].emplace_back(b);G[b].emplace_back(a);}vector<ll> dp(n, -1);dp[0] = n;dfs(G, dp, 0);ll ans = 0;while (q--) {int p;ll x;cin >> p >> x;p--;ans += x * dp[p];cout << ans << '\n';}}