Submission #7012548


Source Code Expand

Copy
#define DEBUG 0
/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 2019/8/18 21:05:45
 * Powered by Visual Studio Code
 */
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
using ll = long long;
class mint
{
public:
  static ll MOD;
  ll x;
  mint() : x(0) {}
  mint(ll x) : x(x % MOD) {}
  mint operator-() const { return x ? MOD - x : 0; }
  mint &operator+=(const mint &a)
  {
    if ((x += a.x) >= MOD)
    {
      x -= MOD;
    }
    return *this;
  }
  mint &operator-=(const mint &a) { return *this += -a; }
  mint &operator*=(const mint &a)
  {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint &operator/=(const mint &a)
  {
    mint b{a};
    return *this *= b.power(MOD - 2);
  }
  mint operator+(const mint &a) const { return mint(*this) += a; }
  mint operator-(const mint &a) const { return mint(*this) -= a; }
  mint operator*(const mint &a) const { return mint(*this) *= a; }
  mint operator/(const mint &a) const { return mint(*this) /= a; }
  bool operator<(const mint &a) const { return x < a.x; }
  bool operator==(const mint &a) const { return x == a.x; }
  const mint power(ll N)
  {
    if (N == 0)
    {
      return 1;
    }
    else if (N % 2 == 1)
    {
      return *this * power(N - 1);
    }
    else
    {
      mint half = power(N / 2);
      return half * half;
    }
  }
};
ll mint::MOD = 1e9 + 7;
istream &operator>>(istream &stream, mint &a) { return stream >> a.x; }
ostream &operator<<(ostream &stream, const mint &a) { return stream << a.x; }
class combination
{
public:
  vector<mint> inv, fact, factinv;
  static int MAX_SIZE;
  combination() : inv(MAX_SIZE), fact(MAX_SIZE), factinv(MAX_SIZE)
  {
    inv[1] = 1;
    for (auto i = 2; i < MAX_SIZE; i++)
    {
      inv[i] = (-inv[mint::MOD % i]) * (mint::MOD / i);
    }
    fact[0] = factinv[0] = 1;
    for (auto i = 1; i < MAX_SIZE; i++)
    {
      fact[i] = mint(i) * fact[i - 1];
      factinv[i] = inv[i] * factinv[i - 1];
    }
  }
  mint operator()(int n, int k)
  {
    if (n >= 0 && k >= 0 && n - k >= 0)
    {
      return fact[n] * factinv[k] * factinv[n - k];
    }
    return 0;
  }
};
int combination::MAX_SIZE = 3000010;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
// constexpr double epsilon = 1e-10;
// constexpr ll infty = 1000000000000000LL;
// constexpr int dx[4] = {1, 0, -1, 0};
// constexpr int dy[4] = {0, 1, 0, -1};
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}
void No()
{
  cout << "No" << endl;
  exit(0);
}

int N;
vector<int> V[200010];
vector<int> children[200010];
int Q;
ll query[200010];
ll ans[200010];

void dfs(int v, int p = -1)
{
  ans[v] = query[v];
  for (auto x : V[v])
  {
    if (x == p)
    {
      continue;
    }
    query[x] += query[v];
    dfs(x, v);
  }
}

int main()
{
  cin >> N >> Q;
  for (auto i = 0; i < N - 1; i++)
  {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    V[a].push_back(b);
    V[b].push_back(a);
  }
  for (auto i = 0; i < Q; i++)
  {
    int p;
    ll x;
    cin >> p >> x;
    --p;
    query[p] += x;
  }
  dfs(0);
  for (auto i = 0; i < N; i++)
  {
    cout << ans[i];
    if (i < N - 1)
    {
      cout << " ";
    }
    else
    {
      cout << endl;
    }
  }
}

Submission Info

Submission Time
Task D - Ki
User kazunetakahashi
Language C++14 (GCC 5.4.1)
Score 400
Code Size 3810 Byte
Status
Exec Time 351 ms
Memory 30464 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02
All 400 / 400 a01, a02, b03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14
Case Name Status Exec Time Memory
a01 4 ms 10752 KB
a02 4 ms 10752 KB
b03 4 ms 10752 KB
b04 351 ms 30336 KB
b05 325 ms 30464 KB
b06 282 ms 20724 KB
b07 237 ms 21748 KB
b08 331 ms 25976 KB
b09 344 ms 20224 KB
b10 349 ms 27136 KB
b11 341 ms 24704 KB
b12 343 ms 22912 KB
b13 348 ms 28800 KB
b14 287 ms 20724 KB