#include <bits/stdc++.h>
// Begin hl/core.hpp
#include <bits/stdc++.h>
using namespace std;
// Utilities
using ll = long long;
const int m197 = 1000000007;
const int m998 = 998244353;
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
template<typename T>
void chmax(T &x, const T &v) {
if (x < v) {
x = v;
}
}
template<typename T>
void chmin(T &x, const T &v) {
if (x > v) {
x = v;
}
}
template<typename T>
int len(const T &x) {
return (int)(x.size());
}
// Debug
void dbg_out() {
cout << endl;
}
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
cout << ' ' << H;
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type
operator<<(Ostream& os, const Cont& v){
os << "[";
for (auto &x : v) {
os << x << ", ";
}
return os << "]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
return os << "{" << p.first << ", " << p.second << "}";
}
// Multi-dimensional vector
template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
static_assert(D >= 1, "Vector dimension must be greater than zero!");
template<typename... Args>
Vec(int n, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};
template<typename T>
struct Vec<1, T> : public vector<T> {
Vec(int n, const T& val = T()) : vector<T>(n, val) {}
};
// Recursive lambda
template<class Fun>
class letrec_result {
Fun fun_;
public:
template<class T>
explicit letrec_result(T &&fun): fun_(std::forward<T>(fun)) {}
template<class ...Args>
decltype(auto) operator()(Args &&...args) {
return fun_(ref(*this), std::forward<Args>(args)...);
}
};
template<class Fun>
decltype(auto) letrec(Fun &&fun) {
return letrec_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
// Input / Output
ll nxt() {
ll x;
cin >> x;
return x;
}
template<typename T>
vector<T> read_vector(int n) {
vector<T> v(n);
for (T &x : v) {
cin >> x;
}
return v;
}
template<typename T>
void print_vector(vector<T> data, bool print_size, bool new_line) {
int n = data.size();
if (print_size) {
cout << n << '\n';
}
for (int i = 0; i < n; ++i) {
cout << data[i] << " \n"[i+1 == n || new_line];
}
}
// End hl/core.hpp
// Begin hl/data/usual.hpp
// Begin hl/data/segtree.hpp
#include <vector>
template<class node, node (*op)(node, node), node (*e)()>
class segtree {
public:
segtree(std::vector<node> v) : _n(v.size()), log(0) {
while ((1 << log) < _n) {
++log;
}
size = (1 << log);
data.assign(2*size, e());
for (int i = 0; i < _n; ++i) {
data[size+i] = v[i];
}
for (int i = size-1; i >= 1; --i) {
update(i);
}
}
segtree(int t = 0, node x = e()) : segtree(std::vector<node>(t, x)) { }
node get(int pos) {
return data[size+pos];
}
void set(int pos, node val) {
pos += size;
data[pos] = val;
for (int i = 1; i <= log; ++i) {
update(pos >> i);
}
}
void refresh(int pos, node proposal) {
set(pos, op(data[size+pos], proposal));
}
node query_semi_open(int left, int right) {
left += size;
right += size;
node res_left = e(), res_right = e();
while (left < right) {
if (left & 1) {
res_left = op(res_left, data[left++]);
}
if (right & 1) {
res_right = op(data[--right], res_right);
}
left >>= 1, right >>= 1;
}
return op(res_left, res_right);
}
node query_all() {
return data[1];
}
private:
int _n, log, size;
std::vector<node> data;
void update(int k) {
data[k] = op(data[k<<1], data[k<<1|1]);
}
};
// End hl/data/segtree.hpp
// Begin hl/data/lazy_segtree.hpp
#include <vector>
#include <cassert>
template<class node,
node (*op)(node, node),
node (*e)(),
class fun,
node (*eval)(fun, node),
fun (*composition)(fun, fun),
fun (*id)()>
class lazy_segtree {
public:
lazy_segtree(std::vector<node> v) : _n(v.size()), log(0) {
while ((1 << log) < _n) {
++log;
}
size = (1 << log);
data.assign(2*size, e());
lazy.assign(size, id());
for (int i = 0; i < _n; ++i) {
data[size + i] = v[i];
}
for (int i = size-1; i >= 1; --i) {
update_one(i);
}
}
lazy_segtree(int t = 0, node x = e()) : lazy_segtree(std::vector<node>(t, x)) { }
node get(int pos) {
int leaf = pos + size;
push_anc(leaf);
return data[leaf];
}
void set(int pos, node val) {
int leaf = pos + size;
push_anc(leaf);
data[leaf] = val;
update_anc(leaf);
}
node query_semi_open(int left, int right) {
left += size;
right += size;
node res_left = e(), res_right = e();
push_anc(left, left);
push_anc(right, right);
while (left < right) {
if (left & 1) {
res_left = op(res_left, data[left++]);
}
if (right & 1) {
res_right = op(data[--right], res_right);
}
left >>= 1;
right >>= 1;
}
return op(res_left, res_right);
}
node query_all() {
return data[1];
}
void apply_one(int pos, fun fct) {
int leaf = pos + size;
push_anc(leaf);
data[leaf] = eval(fct, data[leaf]);
update_anc(leaf);
}
void apply_semi_open(int left, int right, fun fct) {
left += size;
right += size;
if (left == right) {
return;
}
push_anc(left, left);
push_anc(right - 1, right);
int old_left = left, old_right = right;
while (left < right) {
if (left & 1) {
all_apply(left++, fct);
}
if (right & 1) {
all_apply(--right, fct);
}
left >>= 1;
right >>= 1;
}
left = old_left, right = old_right;
update_anc(left, left);
update_anc(right - 1, right);
}
private:
int _n, log, size;
std::vector<node> data;
std::vector<fun> lazy;
void update_one(int k) {
data[k] = op(data[k << 1], data[k << 1 | 1]);
}
void update_anc(int leaf, int dev = 1) {
int s = 1 + __builtin_ctz(dev);
for (int i = s; i <= log; ++i) {
update_one(leaf >> i);
}
}
void all_apply(int k, fun fct) {
data[k] = eval(fct, data[k]);
if (k < size) {
lazy[k] = composition(fct, lazy[k]);
}
}
void push_one(int k) {
all_apply(k << 1, lazy[k]);
all_apply(k << 1 | 1, lazy[k]);
lazy[k] = id();
}
void push_anc(int leaf, int dev = 1) {
int s = 1 + __builtin_ctz(dev);
for (int i = log; i >= s; --i) {
push_one(leaf >> i);
}
}
};
// End hl/data/lazy_segtree.hpp
using ll = long long;
namespace sum32 {
int op(int a, int b) { return a + b; }
int e() { return 0; }
using st = segtree<int, op, e>;
}
namespace min32 {
int op(int a, int b) { return (a < b ? a : b); }
int e() { return -((1<<30)-10); }
using st = segtree<int, op, e>;
}
namespace max32 {
int op(int a, int b) { return (a > b ? a : b); }
int e() { return ((1<<30)-10); }
using st = segtree<int, op, e>;
}
namespace sum64 {
ll op(ll a, ll b) { return a + b; }
ll e() { return 0; }
using st = segtree<ll, op, e>;
}
namespace min64 {
ll op(ll a, ll b) { return (a < b ? a : b); }
ll e() { return -((1LL<<60)-10); }
using st = segtree<ll, op, e>;
}
namespace max64 {
ll op(ll a, ll b) { return (a > b ? a : b); }
ll e() { return ((1LL<<60)-10); }
using st = segtree<ll, op, e>;
}
// End hl/data/usual.hpp
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int nb_node = nxt(), nb_switch = nxt(), nb_query = nxt();
Vec<2, int> adj(nb_node, 0);
vector<pair<int, int>> orig;
rep(id_edge, 0, nb_node - 1) {
int u = nxt() - 1, v = nxt() - 1;
adj[u].push_back(v);
adj[v].push_back(u);
orig.emplace_back(u, v);
}
const int ROOT = 0;
int nb_level = __lg(nb_node) + 1;
Vec<2, int> anc(nb_node, nb_level, -1);
vector<int> tin(nb_node), tout(nb_node);
int timer = 0;
auto build = letrec([&] (auto self, int node) -> void {
tin[node] = timer++;
rep(l, 1, nb_level) {
int t = anc[node][l-1];
if (t == -1) break;
anc[node][l] = anc[t][l-1];
}
for (int child : adj[node]) if (child != anc[node][0]) {
anc[child][0] = node;
self(child);
}
tout[node] = timer++;
});
build(ROOT);
vector<bool> active(nb_node, false);
sum32::st rsum(timer+1, 0);
auto find_root = [&] (int node) {
for (int level = nb_level-1; level >= 0; --level) {
int jto = anc[node][level];
if (jto == -1) continue;
int nb_active = rsum.query_semi_open(tin[jto] + 1, tin[node] + 1);
if (nb_active == 1<<level) {
node = jto;
}
}
return node;
};
auto upd = [&] (int node, int x) {
rsum.set(tin[node], x);
rsum.set(tout[node], -x);
active[node] = x;
};
vector<int> info(nb_node, 1), last_sync(nb_node, 0);
rep(id_switch, 0, nb_switch) {
auto [par, low] = orig[nxt()-1];
if (low == anc[par][0]) swap(par, low);
if (active[low]) {
info[low] = last_sync[low] = info[find_root(low)];
upd(low, 0);
} else {
upd(low, 1);
info[find_root(low)] += info[low] - last_sync[low];
}
}
rep(id_query, 0, nb_query) {
cout << info[find_root(nxt() - 1)] << "\n";
}
}
// File: /home/hugo/Algo/sync/main.cpp
// Last touch: 14:47:24
// Generated: 14:47:25
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
492 KB |
Output is correct |
| 7 |
Correct |
18 ms |
2412 KB |
Output is correct |
| 8 |
Correct |
17 ms |
2412 KB |
Output is correct |
| 9 |
Correct |
17 ms |
2412 KB |
Output is correct |
| 10 |
Correct |
337 ms |
22096 KB |
Output is correct |
| 11 |
Correct |
340 ms |
22096 KB |
Output is correct |
| 12 |
Correct |
385 ms |
29832 KB |
Output is correct |
| 13 |
Correct |
194 ms |
22348 KB |
Output is correct |
| 14 |
Correct |
224 ms |
21968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
26064 KB |
Output is correct |
| 2 |
Correct |
135 ms |
25820 KB |
Output is correct |
| 3 |
Correct |
166 ms |
29776 KB |
Output is correct |
| 4 |
Correct |
168 ms |
29904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
2 ms |
620 KB |
Output is correct |
| 7 |
Correct |
27 ms |
3308 KB |
Output is correct |
| 8 |
Correct |
455 ms |
29960 KB |
Output is correct |
| 9 |
Correct |
465 ms |
30000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
462 ms |
30032 KB |
Output is correct |
| 2 |
Correct |
251 ms |
30456 KB |
Output is correct |
| 3 |
Correct |
249 ms |
30544 KB |
Output is correct |
| 4 |
Correct |
257 ms |
30396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| 5 |
Correct |
2 ms |
492 KB |
Output is correct |
| 6 |
Correct |
25 ms |
2540 KB |
Output is correct |
| 7 |
Correct |
416 ms |
22480 KB |
Output is correct |
| 8 |
Correct |
458 ms |
30032 KB |
Output is correct |
| 9 |
Correct |
219 ms |
22860 KB |
Output is correct |
| 10 |
Correct |
265 ms |
22864 KB |
Output is correct |
| 11 |
Correct |
191 ms |
26704 KB |
Output is correct |
| 12 |
Correct |
185 ms |
26704 KB |
Output is correct |
| 13 |
Correct |
258 ms |
30416 KB |
Output is correct |
