結果
| 問題 | No.1038 TreeAddQuery |
| ユーザー |
 maspy
|
| 提出日時 | 2021-12-31 14:17:15 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,079 ms / 4,000 ms |
| コード長 | 15,857 bytes |
| コンパイル時間 | 4,590 ms |
| コンパイル使用メモリ | 246,992 KB |
| 実行使用メモリ | 29,352 KB |
| 最終ジャッジ日時 | 2024-10-08 11:05:43 |
| 合計ジャッジ時間 | 19,382 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 2 ms
5,248 KB |
| testcase_02 | AC | 2 ms
5,248 KB |
| testcase_03 | AC | 10 ms
5,248 KB |
| testcase_04 | AC | 11 ms
5,248 KB |
| testcase_05 | AC | 9 ms
5,248 KB |
| testcase_06 | AC | 9 ms
5,248 KB |
| testcase_07 | AC | 12 ms
5,248 KB |
| testcase_08 | AC | 587 ms
24,676 KB |
| testcase_09 | AC | 672 ms
25,608 KB |
| testcase_10 | AC | 694 ms
25,068 KB |
| testcase_11 | AC | 682 ms
25,056 KB |
| testcase_12 | AC | 715 ms
25,780 KB |
| testcase_13 | AC | 1,079 ms
25,684 KB |
| testcase_14 | AC | 879 ms
25,820 KB |
| testcase_15 | AC | 836 ms
25,708 KB |
| testcase_16 | AC | 814 ms
25,660 KB |
| testcase_17 | AC | 824 ms
25,548 KB |
| testcase_18 | AC | 176 ms
29,352 KB |
| testcase_19 | AC | 222 ms
25,300 KB |
| testcase_20 | AC | 209 ms
24,808 KB |
| testcase_21 | AC | 254 ms
24,684 KB |
| testcase_22 | AC | 354 ms
24,676 KB |
| testcase_23 | AC | 408 ms
24,776 KB |
| testcase_24 | AC | 705 ms
25,768 KB |
| testcase_25 | AC | 1,073 ms
25,684 KB |
| testcase_26 | AC | 618 ms
27,460 KB |
ソースコード
#line 2 "/home/maspy/library/my_template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ll8 = __int128;
using ld = long double;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
#define vec(type, name, ...) vector<type> name(__VA_ARGS__)
#define VEC(type, name, size) \
vector<type> name(size); \
IN(name)
#define vv(type, name, h, ...) \
vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define VV(type, name, h, w) \
vector<vector<type>> name(h, vector<type>(w)); \
IN(name)
#define vvv(type, name, h, w, ...) \
vector<vector<vector<type>>> name( \
h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...) \
vector<vector<vector<vector<type>>>> name( \
a, vector<vector<vector<type>>>( \
b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i))
#define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i))
#define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i))
#define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i))
#define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(uint x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(ull x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return 31 - __builtin_clz(x); }
int topbit(uint x) { return 31 - __builtin_clz(x); }
int topbit(ll x) { return 63 - __builtin_clzll(x); }
int topbit(ull x) { return 63 - __builtin_clzll(x); }
// (0, 1, 2, 3, 4) -> (32 or 64, 0, 1, 0, 2)
int lowbit(int x) { return 31 - __builtin_clz(x); }
int lowbit(uint x) { return 31 - __builtin_clz(x); }
int lowbit(ll x) { return 63 - __builtin_clzll(x); }
int lowbit(ull x) { return 63 - __builtin_clzll(x); }
ll ceil(ll x, ll y) { return (x > 0 ? (x + y - 1) / y : x / y); }
ll floor(ll x, ll y) { return (x > 0 ? x / y : (x - y + 1) / y); }
pi divmod(ll x, ll y) {
ll q = floor(x, y);
return {q, x - q * y};
}
#define INT(...) \
int __VA_ARGS__; \
IN(__VA_ARGS__)
#define LL(...) \
ll __VA_ARGS__; \
IN(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
IN(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
IN(__VA_ARGS__)
#define DBL(...) \
long double __VA_ARGS__; \
IN(__VA_ARGS__)
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(string &a) { cin >> a; }
template <class T>
void scan(pair<T, T> &p) {
scan(p.first), scan(p.second);
}
template <class T>
void scan(tuple<T, T, T> &p) {
scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p));
}
template <class T>
void scan(tuple<T, T, T, T> &p) {
scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p)), scan(get<3>(p));
}
template <class T>
void scan(vector<T> &a) {
for (auto &i: a) scan(i);
}
template <class T>
void scan(T &a) {
cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &... tail) {
scan(head);
IN(tail...);
}
vi s_to_vi(string S, char first_char = 'a') {
vi A(S.size());
FOR(i, S.size()) { A[i] = S[i] - first_char; }
return A;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &A) {
os << A.fi << " " << A.se;
return os;
}
template <typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &t) {
os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t);
return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &t) {
os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " " << get<3>(t);
return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &A) {
for (size_t i = 0; i < A.size(); i++) {
if (i) os << " ";
os << A[i];
}
return os;
}
void print() { cout << "\n"; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
cout << head;
if (sizeof...(Tail)) cout << " ";
print(forward<Tail>(tail)...);
}
void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
template <typename T>
vector<T> cumsum(vector<T> &A) {
int N = A.size();
vector<T> B(N + 1);
B[0] = T(0);
FOR(i, N) { B[i + 1] = B[i] + A[i]; }
return B;
}
vc<int> bin_count(vi &A, int size) {
vc<int> C(size);
for (auto &x: A) { ++C[x]; }
return C;
}
template <typename T>
vector<int> argsort(vector<T> &A) {
vector<int> ids(A.size());
iota(all(ids), 0);
sort(all(ids),
[&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); });
return ids;
}
ll binary_search(function<bool(ll)> check, ll ok, ll ng) {
assert(check(ok));
while (abs(ok - ng) > 1) {
auto x = (ng + ok) / 2;
if (check(x))
ok = x;
else
ng = x;
}
return ok;
}
template <class T, class S>
inline bool chmax(T &a, const S &b) {
return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
return (a > b ? a = b, 1 : 0);
}
#define SUM(v) accumulate(all(v), 0LL)
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end())
#line 2 "main.cpp"
#line 2 "/home/maspy/library/graph/base.hpp"
template <typename T>
struct Edge {
int frm, to;
T cost;
int id;
};
template <typename T, bool directed = false>
struct Graph {
int N, M;
using cost_type = T;
using edge_type = Edge<T>;
vector<edge_type> edges;
vector<int> indptr;
vector<edge_type> csr_edges;
bool prepared;
class OutgoingEdges {
public:
OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {}
const edge_type* begin() const {
if (l == r) { return 0; }
return &G->csr_edges[l];
}
const edge_type* end() const {
if (l == r) { return 0; }
return &G->csr_edges[r];
}
private:
int l, r;
const Graph* G;
};
bool is_prepared() { return prepared; }
constexpr bool is_directed() { return directed; }
Graph() {}
Graph(int N) : N(N), M(0), prepared(0) {}
void add(int frm, int to, T cost = 1, int i = -1) {
assert(!prepared);
assert(0 <= frm && frm < N && 0 <= to && to < N);
if (i == -1) i = M;
auto e = edge_type({frm, to, cost, i});
edges.eb(e);
++M;
}
void prepare() {
assert(!prepared);
prepared = true;
indptr.assign(N + 1, 0);
for (auto&& e: edges) {
indptr[e.frm + 1]++;
if (!directed) indptr[e.to + 1]++;
}
FOR(v, N) indptr[v + 1] += indptr[v];
auto counter = indptr;
csr_edges.resize(indptr.back() + 1);
for (auto&& e: edges) {
csr_edges[counter[e.frm]++] = e;
if (!directed)
csr_edges[counter[e.to]++] = edge_type({e.to, e.frm, e.cost, e.id});
}
}
OutgoingEdges operator[](int v) const {
assert(prepared);
return {this, indptr[v], indptr[v + 1]};
}
void debug() {
print("Graph");
if (!prepared) {
print("frm to cost id");
for (auto&& e: edges) print(e.frm, e.to, e.cost, e.id);
} else {
print("indptr", indptr);
print("frm to cost id");
FOR(v, N) for (auto&& e: (*this)[v]) print(e.frm, e.to, e.cost, e.id);
}
}
int size() { return N; }
};
#line 1 "/home/maspy/library/ds/fastset.hpp"
struct FastSet {
using uint = unsigned;
using ull = unsigned long long;
int bsr(ull x) { return 63 - __builtin_clzll(x); }
int bsf(ull x) { return __builtin_ctzll(x); }
static constexpr uint B = 64;
int n, lg;
vc<vc<ull>> seg;
FastSet(int _n) : n(_n) {
do {
seg.push_back(vc<ull>((_n + B - 1) / B));
_n = (_n + B - 1) / B;
} while (_n > 1);
lg = int(seg.size());
}
bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; }
void insert(int i) {
for (int h = 0; h < lg; h++) {
seg[h][i / B] |= 1ULL << (i % B);
i /= B;
}
}
void erase(int i) {
for (int h = 0; h < lg; h++) {
seg[h][i / B] &= ~(1ULL << (i % B));
if (seg[h][i / B])
break;
i /= B;
}
}
// x以上最小の要素
int next(int i) {
for (int h = 0; h < lg; h++) {
if (i / B == seg[h].size())
break;
ull d = seg[h][i / B] >> (i % B);
if (!d) {
i = i / B + 1;
continue;
}
// find
i += bsf(d);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += bsf(seg[g][i / B]);
}
return i;
}
return n;
}
// x以下最大の要素
int prev(int i) {
if(i < 0) return -1;
chmin(i, n - 1);
for (int h = 0; h < lg; h++) {
if (i == -1)
break;
ull d = seg[h][i / B] << (63 - i % 64);
if (!d) {
i = i / B - 1;
continue;
}
// find
i += bsr(d) - (B - 1);
for (int g = h - 1; g >= 0; g--) {
i *= B;
i += bsr(seg[g][i / B]);
}
return i;
}
return -1;
}
void print(){
for(int i=0;i<n;++i) cout << (*this)[i];
cout << endl;
}
};
#line 1 "/home/maspy/library/algebra/addgroup.hpp"
template <class X, X ZERO = X(0)>
struct AddGroup {
using value_type = X;
static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
static constexpr X inverse(const X &x) noexcept { return -x; }
static constexpr X power(const X &x, ll n) noexcept { return n * x; }
static constexpr X unit = ZERO;
static constexpr bool commute = true;
};
#line 2 "/home/maspy/library/ds/fenwick.hpp"
template <typename AbelGroup>
struct FenwickTree {
using E = typename AbelGroup::value_type;
int n;
vector<E> dat;
E total;
FenwickTree() : FenwickTree(0) {}
FenwickTree(int n) : n(n), total(AbelGroup::unit) {
assert(AbelGroup::commute);
dat.assign(n, AbelGroup::unit);
}
FenwickTree(vc<E> v) : n(len(v)), total(AbelGroup::unit) {
assert(AbelGroup::commute);
dat = v;
FOR3(i, 1, n + 1) {
int j = i + (i & -i);
if (j <= n) dat[j - 1] = AbelGroup::op(dat[i - 1], dat[j - 1]);
}
}
E sum(int k) {
E ret = AbelGroup::unit;
for (; k > 0; k -= k & -k) ret = AbelGroup::op(ret, dat[k - 1]);
return ret;
}
E sum(int L, int R) {
E pos = AbelGroup::unit;
while (L < R) {
pos = AbelGroup::op(pos, dat[R - 1]);
R -= R & -R;
}
E neg = AbelGroup::unit;
while (R < L) {
neg = AbelGroup::op(neg, dat[L - 1]);
L -= L & -L;
}
return AbelGroup::op(pos, AbelGroup::inverse(neg));
}
E sum_all() { return total; }
void add(int k, E x) {
total = AbelGroup::op(total, x);
for (++k; k <= n; k += k & -k) dat[k - 1] = AbelGroup::op(dat[k - 1], x);
}
template <class F>
int max_right(F& check) {
assert(f(E(0)));
ll i = 0;
E s = AbelGroup::unit;
int k = 1;
int N = len(dat) + 1;
while (2 * k < N) k *= 2;
while (k) {
if (i + k < N && check(AbelGroup::op(s, dat[i + k - 1]))) {
i += k;
s = AbelGroup::op(s, dat[i - 1]);
}
k >>= 1;
}
return i;
}
int find_kth_element(E k) {
auto check = [&](E x) -> bool { return x < k; };
return max_right(check);
}
void debug() { print("fenwick", dat); }
};
#line 7 "main.cpp"
template <typename Graph, typename E = int>
struct CentroidDecomposition {
using edge_type = typename Graph::edge_type;
using F = function<E(E, edge_type)>;
Graph& G;
F f; // (E path value, edge e) -> E new_path_value
int N;
vector<int> cdep; // depth in centroid tree
vc<int> sz;
vc<int> par;
CentroidDecomposition(
Graph& G, F f = [](int x, edge_type e) { return x + e.cost; })
: G(G), N(G.N), f(f), sz(G.N), par(G.N), cdep(G.N, -1) {
build();
}
int find(int v) {
vc<int> V = {v};
par[v] = -1;
int p = 0;
while (p < len(V)) {
int v = V[p++];
sz[v] = 0;
for (auto&& e: G[v]) {
if (e.to == par[v] || cdep[e.to] != -1) continue;
par[e.to] = v;
V.eb(e.to);
}
}
while (len(V)) {
int v = V.back();
V.pop_back();
sz[v] += 1;
if (p - sz[v] <= p / 2) return v;
sz[par[v]] += sz[v];
}
return -1;
}
void build() {
assert(G.is_prepared());
assert(!G.is_directed());
int N = G.N;
vc<pair<int, int>> st = {{0, 0}};
while (len(st)) {
auto [lv, v] = st.back();
st.pop_back();
auto c = find(v);
cdep[c] = lv;
for (auto&& [frm, to, cost, id]: G[c]) {
if (cdep[to] == -1) st.eb(lv + 1, to);
}
}
}
vc<vc<pair<int, E>>> collect(int root, E root_val) {
/*
root を重心とする木において、(v, path data v) の vector を、方向ごとに集めて返す
・0 番目：root からのパスすべて（root を含む）
・i 番目：i 番目の方向
*/
vc<vc<pair<int, E>>> res = {{{root, root_val}}};
for (auto&& e: G[root]) {
int nxt = e.to;
if (cdep[nxt] < cdep[root]) continue;
vc<pair<int, E>> dat;
int p = 0;
dat.eb(nxt, f(root_val, e));
par[nxt] = root;
while (p < len(dat)) {
auto [v, val] = dat[p++];
for (auto&& e: G[v]) {
if (e.to == par[v]) continue;
if (cdep[e.to] < cdep[root]) continue;
par[e.to] = v;
dat.eb(e.to, f(val, e));
}
}
res.eb(dat);
res[0].insert(res[0].end(), all(dat));
}
return res;
}
};
void solve() {
LL(N, Q);
Graph<int> G(N);
FOR(_, N - 1) {
LL(a, b);
G.add(--a, --b);
}
G.prepare();
using T = tuple<ll, ll, ll>;
VEC(T, query, Q);
for (auto&& [a, b, c]: query) --a;
// 頂点 -> クエリ
vc<vi> query_at(N);
FOR(q, Q) query_at[get<0>(query[q])].eb(q);
CentroidDecomposition CD(G);
vi ANS(Q);
FenwickTree<AddGroup<ll>> bit(N + 10);
FOR(root, N) {
auto dats = CD.collect(root, 0);
FOR(i, len(dats)) {
auto dat = dats[i];
// qid, v, dv
vc<T> event;
for (auto&& [v, dv]: dat) {
for (auto&& q: query_at[v]) { event.eb(q, v, dv); }
}
sort(all(event));
for (auto&& [qid, v, dv]: event) {
auto [_, y, z] = query[qid];
ll add = bit.sum(0, dv + 1);
ANS[qid] += (i == 0 ? add : -add);
if (dv <= y) {
bit.add(0, z);
bit.add(y - dv + 1, -z);
}
}
for (auto&& [qid, v, dv]: event) {
auto [_, y, z] = query[qid];
if (dv <= y) {
bit.add(0, -z);
bit.add(y - dv + 1, +z);
}
}
}
}
for (auto&& x: ANS) print(x);
}
signed main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << setprecision(15);
ll T = 1;
// LL(T);
FOR(_, T) solve();
return 0;
}