結果
| 問題 | No.899 γatheree |
| ユーザー |
 maspy
|
| 提出日時 | 2021-12-30 19:46:43 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 16,244 bytes |
| コンパイル時間 | 3,380 ms |
| コンパイル使用メモリ | 227,184 KB |
| 実行使用メモリ | 16,484 KB |
| 最終ジャッジ日時 | 2024-04-16 04:31:44 |
| 合計ジャッジ時間 | 13,899 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | RE | - |
| testcase_02 | RE | - |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | RE | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | RE | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | RE | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
ソースコード
#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 "/home/maspy/library/graph/base.hpp"
// frm, to, cap, cost
template <typename T>
using Edge = tuple<int, int, T, int>;
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);
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&& [frm, to, cost, id]: edges) {
indptr[frm + 1]++;
if (!directed) indptr[to + 1]++;
}
FOR(v, N) indptr[v + 1] += indptr[v];
auto counter = indptr;
csr_edges.resize(indptr.back() + 1);
for (auto&& [frm, to, cost, id]: edges) {
csr_edges[counter[frm]++] = {frm, to, cost, id};
if (!directed) csr_edges[counter[to]++] = {to, frm, cost, 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);
} else {
print("indptr", indptr);
print("frm to cost id");
FOR(v, N) for (auto&& e: (*this)[v]) print(e);
}
}
int size() { return N; }
};
#line 2 "/home/maspy/library/graph/bfsnumbering.hpp"
template <typename Graph>
struct BFSNumbering {
Graph& G;
int root;
vector<int> V;
vector<int> ID;
vector<int> depth;
vector<int> parent;
vector<int> LID, RID;
vector<int> LID_seq;
vector<int> dep_ids;
int cnt;
BFSNumbering(Graph& G, int root = 0) : G(G), root(root), cnt(0) { build(); }
void bfs() {
deque<int> que = {root};
while (!que.empty()) {
int v = que.front();
que.pop_front();
ID[v] = V.size();
V.eb(v);
for(auto&& [frm,to,cost,id] : G[v]) {
if (to == parent[v]) continue;
que.emplace_back(to);
parent[to] = v;
depth[to] = depth[v] + 1;
}
}
}
void dfs(int v) {
LID[v] = cnt++;
for(auto&& [frm,to,cost,id] : G[v]) {
if (to == parent[v]) continue;
dfs(to);
}
RID[v] = cnt;
}
void build() {
int N = G.N;
V.reserve(N);
parent.assign(N, -1);
ID.assign(N, 0);
LID.assign(N, 0);
RID.assign(N, 0);
depth.assign(N, 0);
bfs();
dfs(root);
int D = MAX(depth);
dep_ids.resize(D + 2);
FOR(v, N) dep_ids[depth[v] + 1]++;
FOR(d, D + 1) dep_ids[d + 1] += dep_ids[d];
LID_seq.reserve(N);
FOR(i, N) LID_seq.eb(LID[V[i]]);
}
int bs(int L, int R, int x) {
while (L + 1 < R) {
int M = (L + R) / 2;
if (LID_seq[M] >= x)
R = M;
else
L = M;
}
return R;
}
pair<int, int> calc_range(int v, int dep) {
assert(dep >= depth[v]);
if (dep >= len(dep_ids) - 1) return {0, 0};
int l = LID[v], r = RID[v];
int L = dep_ids[dep], R = dep_ids[dep + 1];
int a = bs(L - 1, R, l);
int b = bs(L - 1, R, r);
return {a, b};
}
};
#line 2 "/home/maspy/library/ds/lazysegtree.hpp"
template <typename Lazy>
struct LazySegTree {
using Monoid_X = typename Lazy::X_structure;
using Monoid_A = typename Lazy::A_structure;
using X = typename Monoid_X::value_type;
using A = typename Monoid_A::value_type;
int n, log, size;
vc<X> dat;
vc<A> laz;
LazySegTree() : LazySegTree(0) {}
LazySegTree(int n) : LazySegTree(vc<X>(n, Monoid_X::unit)) {}
LazySegTree(vc<X> v) : n(len(v)) {
log = 1;
while ((1 << log) < n) ++log;
size = 1 << log;
dat.assign(size << 1, Monoid_X::unit);
laz.assign(size, Monoid_A::unit);
FOR(i, n) dat[size + i] = v[i];
FOR3_R(i, 1, size) update(i);
}
void update(int k) { dat[k] = Monoid_X::op(dat[2 * k], dat[2 * k + 1]); }
void all_apply(int k, A a) {
dat[k] = Lazy::act(dat[k], a);
if (k < size) laz[k] = Monoid_A::op(laz[k], a);
}
void push(int k) {
all_apply(2 * k, laz[k]);
all_apply(2 * k + 1, laz[k]);
laz[k] = Monoid_A::unit;
}
void set(int p, X x) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
dat[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
X get(int p) {
assert(0 <= p && p < n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return dat[p];
}
vc<X> get_all() {
FOR(i, size) push(i);
return {dat.begin() + size, dat.begin() + size + n};
}
X prod(int l, int r) {
assert(0 <= l && l <= r && r <= n);
if (l == r) return Monoid_X::unit;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
X xl = Monoid_X::unit, xr = Monoid_X::unit;
while (l < r) {
if (l & 1) xl = Monoid_X::op(xl, dat[l++]);
if (r & 1) xr = Monoid_X::op(dat[--r], xr);
l >>= 1;
r >>= 1;
}
return Monoid_X::op(xl, xr);
}
X all_prod() { return dat[1]; }
void apply(int p, A a) {
assert(0 <= p && p < n);
p += size;
if (!Monoid_A::commute)
for (int i = log; i >= 1; i--) push(p >> i);
dat[p] = Lazy::act(dat[p], a);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, A a) {
assert(0 <= l && l <= r && r <= n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, a);
if (r & 1) all_apply(--r, a);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <typename C>
int max_right(C& check, int l) {
assert(0 <= l && l <= n);
assert(check(Monoid_X::unit));
if (l == n) return n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
X sm = Monoid_X::unit;
do {
while (l % 2 == 0) l >>= 1;
if (!check(Monoid_X::op(sm, dat[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (check(Monoid_X::op(sm, dat[l]))) {
sm = Monoid_X::op(sm, dat[l]);
l++;
}
}
return l - size;
}
sm = Monoid_X::op(sm, dat[l]);
l++;
} while ((l & -l) != l);
return n;
}
template <typename C>
int min_left(C& check, int r) {
assert(0 <= r && r <= n);
assert(check(Monoid_X::unit));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
X sm = Monoid_X::unit;
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!check(Monoid_X::op(dat[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (check(Monoid_X::op(dat[r], sm))) {
sm = Monoid_X::op(dat[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = Monoid_X::op(dat[r], sm);
} while ((r & -r) != r);
return 0;
}
void debug() { print("lazysegtree getall:", get_all()); }
};
#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 unit = ZERO;
static constexpr bool commute = true;
};
#line 1 "/home/maspy/library/algebra/mulgroup.hpp"
template <class X, X ONE = X(1)>
struct MulGroup {
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(1) / x; }
static constexpr X unit = ONE;
static constexpr bool commute = true;
};
#line 6 "main.cpp"
template <typename E>
struct Add_Mul {
using MX = AddGroup<E>;
using MA = MulGroup<E>;
using X_structure = MX;
using A_structure = MA;
using X = typename MX::value_type;
using A = typename MA::value_type;
static constexpr X act(const X &x, const A &a) { return x * a; }
};
void solve() {
LL(N);
Graph<int> G(N);
FOR(_, N - 1) {
LL(a, b);
G.add(a, b);
}
G.prepare();
VEC(ll, A, N);
BFSNumbering BFS(G);
auto &ID = BFS.ID;
using Lazy = Add_Mul<ll>;
LazySegTree<Lazy> seg(N);
FOR(v, N) seg.set(ID[v], A[v]);
LL(Q);
FOR(_, Q) {
LL(v);
ll p = BFS.parent[v];
ll pp = (p == -1 ? -1 : BFS.parent[p]);
ll x = 0;
if (pp >= 0) x += seg.get(ID[pp]), seg.set(ID[pp], 0);
if (p >= 0) {
x += seg.get(ID[p]), seg.set(ID[p], 0);
auto [l, r] = BFS.calc_range(p, 1);
x += seg.prod(l, r), seg.apply(l, r, 0);
}
FOR(d, 3) {
auto [l, r] = BFS.calc_range(v, BFS.depth[v] + d);
x += seg.prod(l, r), seg.apply(l, r, 0);
}
print(x);
seg.set(ID[v], x);
}
}
signed main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << setprecision(15);
ll T = 1;
// LL(T);
FOR(_, T) solve();
return 0;
}