結果
| 問題 |
No.1637 Easy Tree Query
|
| コンテスト | |
| ユーザー |
 stoq
|
| 提出日時 | 2021-08-06 21:25:23 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 64 ms / 2,000 ms |
| コード長 | 6,152 bytes |
| コンパイル時間 | 2,421 ms |
| コンパイル使用メモリ | 212,936 KB |
| 最終ジャッジ日時 | 2025-01-23 14:31:59 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 33 |
ソースコード
#define MOD_TYPE 1
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
#if 1
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <typename T>
using extset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#if 0
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using Int = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;
#endif
using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename T>
using smaller_queue = priority_queue<T, vector<T>, greater<T>>;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9 + 10;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-7;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};
#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";
struct io_init
{
io_init()
{
cin.tie(0);
ios::sync_with_stdio(false);
cout << setprecision(30) << setiosflags(ios::fixed);
};
} io_init;
template <typename T>
inline bool chmin(T &a, T b)
{
if (a > b)
{
a = b;
return true;
}
return false;
}
template <typename T>
inline bool chmax(T &a, T b)
{
if (a < b)
{
a = b;
return true;
}
return false;
}
inline ll CEIL(ll a, ll b)
{
return (a + b - 1) / b;
}
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val)
{
fill((T *)array, (T *)(array + N), val);
}
template <typename T, typename U>
constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept
{
is >> p.first >> p.second;
return is;
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> &p) noexcept
{
os << p.first << " " << p.second;
return os;
}
#pragma endregion
random_device seed_gen;
mt19937_64 engine(seed_gen());
// --------------------------------------
template <typename T>
struct Tree
{
int V;
using P = pair<int, T>;
vector<vector<P>> E;
vector<int> par, depth, in, out;
vector<T> dist;
vector<vector<int>> par_double;
Tree(int V) : V(V)
{
E.resize(V);
depth.resize(V);
dist.resize(V);
in.resize(V);
out.resize(V);
}
void read(int index = 1, bool ini = true)
{
int a, b;
for (int i = 0; i < V - 1; i++)
{
cin >> a >> b, a -= index, b -= index;
E[a].push_back({b, 1});
E[b].push_back({a, 1});
}
if (ini)
init();
}
void add_edge(int a, int b, T w = 1)
{
E[a].push_back({b, w});
E[b].push_back({a, w});
}
void dfs(int v, int d, T w, int &i)
{
in[v] = i++;
depth[v] = d;
dist[v] = w;
for (auto [c, di] : E[v])
{
if (par[v] == c)
continue;
par[c] = v;
dfs(c, d + 1, w + di, i);
}
out[v] = i;
}
inline int sub(int v) { return out[v] - in[v]; }
void init(int root = 0)
{
calculated = false;
par.assign(V, -1);
int i = 0;
dfs(root, 0, 0, i);
}
bool calculated;
void calc_double()
{
par_double.assign(V, vector<int>(25));
for (int i = 0; i < V; i++)
par_double[i][0] = par[i];
for (int k = 0; k < 24; k++)
{
for (int i = 0; i < V; i++)
{
if (par_double[i][k] == -1)
par_double[i][k + 1] = -1;
else
par_double[i][k + 1] = par_double[par_double[i][k]][k];
}
}
}
int getLCA(int a, int b)
{
if (!calculated)
calc_double(), calculated = true;
if (a == b)
return a;
if (depth[a] < depth[b])
swap(a, b);
for (int k = 24; k >= 0; k--)
{
if (par_double[a][k] != -1 && depth[par_double[a][k]] >= depth[b])
a = par_double[a][k];
}
if (a == b)
return a;
for (int k = 24; k >= 0; k--)
{
if (par_double[a][k] != -1 && par_double[a][k] != par_double[b][k])
{
a = par_double[a][k];
b = par_double[b][k];
}
}
return par_double[a][0];
}
int length(int a, int b) { return depth[a] + depth[b] - 2 * depth[getLCA(a, b)]; }
T distance(int a, int b) { return dist[a] + dist[b] - 2 * dist[getLCA(a, b)]; }
T diameter(int &a, int &b)
{
T Max(-1), d;
for (int i = 0; i < V; i++)
{
d = distance(0, i);
if (Max < d)
Max = d, a = i;
}
for (int i = 0; i < V; i++)
{
d = distance(a, i);
if (Max < d)
Max = d, b = i;
}
return Max;
}
T diameter()
{
int a, b;
return diameter(a, b);
}
int unweighted_diameter(int &a, int &b)
{
int Max = 1, d;
for (int i = 0; i < V; i++)
{
d = length(0, i);
if (Max < d)
Max = d, a = i;
}
for (int i = 0; i < V; i++)
{
d = length(a, i);
if (Max < d)
Max = d, b = i;
}
return Max;
}
int unweighted_diameter()
{
int a, b;
return unweighted_diameter(a, b);
}
};
void solve()
{
int n, q;
cin >> n >> q;
Tree<int> tr(n);
rep(i, n - 1)
{
int a, b;
cin >> a >> b;
a--, b--;
tr.add_edge(a, b);
}
tr.init();
ll sum = 0;
rep(i, q)
{
int p;
ll x;
cin >> p >> x;
p--;
sum += x * tr.sub(p);
cout << sum << "\n";
}
}
int main()
{
solve();
}