結果

問題 No.1637 Easy Tree Query
ユーザー hanyuhanyu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0