#include <bits/stdc++.h>
using namespace std;
template<class C>constexpr int sz(const C&c){return int(c.size());}
using ll=long long;constexpr const char nl='\n',sp=' ';
template <class _Node, class Container = deque<_Node>> struct Splay {
using Node = _Node; Container TR; deque<Node*> deleted;
static_assert(Node::HAS_PAR, "Splay Node must have parent pointer");
template <class T> Node *makeNode(const T &v) {
if (deleted.empty()) { TR.emplace_back(v); return &TR.back(); }
Node *x = deleted.back(); deleted.pop_back();
*x = typename Container::value_type(v); return x;
}
bool isRoot(Node *x) { return !x->p || (x != x->p->l && x != x->p->r); }
void connect(Node *x, Node *p, bool hasCh, bool isL) {
if (x) x->p = p;
if (hasCh) (isL ? p->l : p->r) = x;
}
void rotate(Node *x) {
Node *p = x->p, *g = p->p; bool isRootP = isRoot(p), isL = x == p->l;
connect(isL ? x->r : x->l, p, true, isL); connect(p, x, true, !isL);
connect(x, g, !isRootP, !isRootP && p == g->l); p->update();
}
void splay(Node *x) {
while (!isRoot(x)) {
Node *p = x->p, *g = p->p; if (!isRoot(p)) g->propagate();
p->propagate(); x->propagate();
if (!isRoot(p)) rotate((x == p->l) == (p == g->l) ? p : x);
rotate(x);
}
x->propagate(); x->update();
}
template <class F> void applyToRange(Node *&root, int i, int j, F f) {
int sz = root ? root->sz : 0;
if (i <= 0 && sz - 1 <= j) {
f(root); if (root) { root->propagate(); root->update(); }
} else if (i <= 0) {
Node *l = select(root, j + 1)->l; connect(nullptr, root, true, true);
root->update(); connect(l, nullptr, false, true); f(l);
if (l) { l->propagate(); l->update(); }
connect(l, root, true, true); root->update();
} else if (sz - 1 <= j) {
Node *r = select(root, i - 1)->r; connect(nullptr, root, true, false);
root->update(); connect(r, nullptr, false, false); f(r);
if (r) { r->propagate(); r->update(); }
connect(r, root, true, false); root->update();
} else {
Node *r = select(root, i - 1)->r; connect(nullptr, root, true, false);
root->update(); connect(r, nullptr, false, false);
Node *l = select(r, j - i + 1)->l; connect(nullptr, r, true, true);
r->update(); connect(l, nullptr, false, true); f(l);
if (l) { l->propagate(); l->update(); }
connect(l, r, true, true); r->update(); connect(r, root, true, false);
root->update();
}
}
Node *select(Node *&root, int k) {
Node *last = nullptr; while (root) {
(last = root)->propagate(); int t = root->l ? root->l->sz : 0;
if (t > k) root = root->l;
else if (t < k) { root = root->r; k -= t + 1; }
else break;
}
if (root) splay(root);
else if (last) splay(root = last);
return root;
}
int index(Node *&root, Node *x) {
root = x; if (!root) return -1;
splay(root); return root->l ? root->l->sz : 0;
}
template <class T, class Comp>
pair<int, Node *> getFirst(Node *&root, const T &v, Comp cmp) {
pair<int, Node *> ret(0, nullptr); Node *last = nullptr;
for (Node *x = root; x;) {
(last = x)->propagate();
if (!cmp(x->val, v)) { root = ret.second = x; x = x->l; }
else { ret.first += 1 + (x->l ? x->l->sz : 0); x = x->r; }
}
if (root) splay(root);
else if (last) splay(root = last);
return ret;
}
template <class F> Node *buildRec(int l, int r, F &f) {
if (l > r) return nullptr;
int m = l + (r - l) / 2; Node *left = buildRec(l, m - 1, f);
Node *ret = makeNode(f()), *right = buildRec(m + 1, r, f);
connect(left, ret, ret, true); connect(right, ret, ret, false);
ret->update(); return ret;
}
template <class F> Node *build(int l, int r, F f) {
return buildRec(l, r, f);
}
void clear(Node *x) {
if (!x) return;
clear(x->l); deleted.push_back(x); clear(x->r);
}
};
template <class Node> struct LinkCutTree : public Splay<Node, vector<Node>> {
using Tree = Splay<Node, vector<Node>>;
using Tree::TR; using Tree::makeNode; using Tree::splay; using Tree::select;
using Data = typename Node::Data; using Lazy = typename Node::Lazy;
int vert(Node *x) { return x - TR.data(); }
Node *access(Node *x) {
Node *last = nullptr;
for (Node *y = x; y; y = y->p) { splay(y); y->r = last; last = y; }
splay(x); return last;
}
template <const int _ = Node::RANGE_REVERSALS>
typename enable_if<_>::type makeRoot(Node *x) { access(x); x->reverse(); }
Node *findMin(Node *x) {
for (x->propagate(); x->l; (x = x->l)->propagate());
splay(x); return x;
}
Node *findMax(Node *x) {
for (x->propagate(); x->r; (x = x->r)->propagate());
splay(x); return x;
}
template <const int _ = Node::RANGE_REVERSALS>
typename enable_if<_>::type makeRoot(int x) { makeRoot(&TR[x]); }
int lca(int x, int y) {
if (x == y) return x;
access(&TR[x]); Node *ny = access(&TR[y]); return TR[x].p ? vert(ny) : -1;
}
bool connected(int x, int y) { return lca(x, y) != -1; }
template <const int _ = Node::RANGE_REVERSALS>
typename enable_if<_>::type link(int x, int y) {
makeRoot(y); TR[y].p = &TR[x];
}
template <const int _ = Node::RANGE_REVERSALS>
typename enable_if<_, bool>::type safeLink(int x, int y) {
if (connected(x, y)) return false;
link(x, y); return true;
}
bool linkParent(int par, int ch) {
access(&TR[ch]); if (TR[ch].l) return false;
TR[ch].p = &TR[par]; return true;
}
template <const int _ = Node::RANGE_REVERSALS>
typename enable_if<_, bool>::type cut(int x, int y) {
makeRoot(x); access(&TR[y]);
if (&TR[x] != TR[y].l || TR[x].r) return false;
TR[y].l->p = nullptr; TR[y].l = nullptr; return true;
}
bool cutParent(int x) {
access(&TR[x]); if (!TR[x].l) return false;
TR[x].l->p = nullptr; TR[x].l = nullptr; return true;
}
int findParent(int x) {
access(&TR[x]); return TR[x].l ? vert(findMax(TR[x].l)) : -1;
}
int findRoot(int x) { access(&TR[x]); return vert(findMin(&TR[x])); }
int depth(int x) { access(&TR[x]); return TR[x].l ? TR[x].l->sz : 0; }
int kthParent(int x, int k) {
int d = depth(x); Node *nx = &TR[x];
return k <= d ? vert(select(nx, d - k)) : -1;
}
void updateVertex(int x, const Lazy &v) {
access(&TR[x]); Node *l = TR[x].l; TR[x].l = nullptr;
TR[x].apply(v); TR[x].propagate(); TR[x].update(); TR[x].l = l;
}
template <const int _ = Node::RANGE_UPDATES>
typename enable_if<_>::type updatePathFromRoot(int to, const Lazy &v) {
access(&TR[to]); TR[to].apply(v);
}
template <const int _ = Node::RANGE_UPDATES && Node::RANGE_REVERSALS>
typename enable_if<_, bool>::type updatePath(
int from, int to, const Lazy &v) {
makeRoot(from); access(&TR[to]);
if (from != to && !TR[from].p) return false;
TR[to].apply(v); return true;
}
Data queryVertex(int x) { access(&TR[x]); return TR[x].val; }
template <const int _ = Node::RANGE_QUERIES>
typename enable_if<_, Data>::type queryPathFromRoot(int to) {
access(&TR[to]); return TR[to].sbtr;
}
template <const int _ = Node::RANGE_QUERIES && Node::RANGE_REVERSALS>
typename enable_if<_, Data>::type queryPath(int from, int to) {
makeRoot(from); access(&TR[to]);
return from == to || TR[from].p ? TR[to].sbtr : Node::qdef();
}
template <class F> LinkCutTree(int N, F f) {
TR.reserve(N); for (int i = 0; i < N; i++) makeNode(f());
}
template <class It> LinkCutTree(It st, It en)
: LinkCutTree(en - st, [&] { *st++; }) {}
};
template <class T> struct NodeVal {
using Data = T;
using Lazy = Data;
const static int RANGE_UPDATES = false;
const static int RANGE_QUERIES = false;
const static int RANGE_REVERSALS = false;
const static int HAS_PAR = true;
int sz; NodeVal *l, *r, *p; Data val;
NodeVal(const Data &v)
: sz(1), l(nullptr), r(nullptr), p(nullptr), val(v) {}
void update() {
sz = 1;
if (l) sz += l->sz;
if (r) sz += r->sz;
}
void propagate() {}
void apply(const Lazy &v) { val = v; }
};
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// freopen("err.txt", "w", stderr);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
vector<bool> active(N - 1, false);
vector<vector<int>> adj(N);
vector<pair<int, int>> E;
vector<int> cnt(N, 1), last(N, 0);
for (int i = 0; i < N - 1; i++) {
int a, b;
cin >> a >> b;
E.emplace_back(--a, --b);
adj[a].push_back(i);
adj[b].push_back(i);
}
function<void(int, int)> dfs = [&] (int v, int prev) {
for (int i : adj[v]) {
if (E[i].first == prev || E[i].second == prev) continue;
if (E[i].second == v) swap(E[i].first, E[i].second);
dfs(E[i].second, v);
}
};
dfs(0, -1);
struct null_type {};
LinkCutTree<NodeVal<null_type>> LCT(N, [&] { return null_type(); });
for (int i = 0; i < M; i++) {
int j;
cin >> j;
--j;
if (active[j]) {
last[E[j].second] = cnt[LCT.findRoot(E[j].first)];
LCT.cutParent(E[j].second);
cnt[E[j].second] = last[E[j].second];
} else {
cnt[LCT.findRoot(E[j].first)] += cnt[E[j].second] - last[E[j].second];
LCT.linkParent(E[j].first, E[j].second);
}
active[j] = !active[j];
}
for (int i = 0; i < Q; i++) {
int c;
cin >> c;
cout << cnt[LCT.findRoot(--c)] << nl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
6 ms |
512 KB |
Output is correct |
| 7 |
Correct |
12 ms |
1664 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1664 KB |
Output is correct |
| 9 |
Correct |
12 ms |
1664 KB |
Output is correct |
| 10 |
Correct |
116 ms |
13676 KB |
Output is correct |
| 11 |
Correct |
115 ms |
13884 KB |
Output is correct |
| 12 |
Correct |
95 ms |
19960 KB |
Output is correct |
| 13 |
Correct |
76 ms |
13676 KB |
Output is correct |
| 14 |
Correct |
94 ms |
13168 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
16748 KB |
Output is correct |
| 2 |
Correct |
73 ms |
16492 KB |
Output is correct |
| 3 |
Correct |
69 ms |
19312 KB |
Output is correct |
| 4 |
Correct |
67 ms |
19308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
512 KB |
Output is correct |
| 7 |
Correct |
13 ms |
2304 KB |
Output is correct |
| 8 |
Correct |
126 ms |
20720 KB |
Output is correct |
| 9 |
Correct |
126 ms |
20716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
20720 KB |
Output is correct |
| 2 |
Correct |
93 ms |
20332 KB |
Output is correct |
| 3 |
Correct |
97 ms |
20588 KB |
Output is correct |
| 4 |
Correct |
94 ms |
20460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
512 KB |
Output is correct |
| 6 |
Correct |
14 ms |
1792 KB |
Output is correct |
| 7 |
Correct |
143 ms |
14572 KB |
Output is correct |
| 8 |
Correct |
124 ms |
20588 KB |
Output is correct |
| 9 |
Correct |
99 ms |
14828 KB |
Output is correct |
| 10 |
Correct |
173 ms |
14444 KB |
Output is correct |
| 11 |
Correct |
99 ms |
17900 KB |
Output is correct |
| 12 |
Correct |
97 ms |
17900 KB |
Output is correct |
| 13 |
Correct |
98 ms |
20588 KB |
Output is correct |
