#include <bits/stdc++.h>
#define ll long long int
#define ld long double
const ll MOD = 998244353;
const ll INF = 1e18;
using namespace std;
vector<string> vec_splitter(string s) {
s += ',';
vector<string> res;
while(!s.empty()) {
res.push_back(s.substr(0, s.find(',')));
s = s.substr(s.find(',') + 1);
}
return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx,
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
stringstream ss; ss << H;
cerr << args[idx] << " = " << ss.str();
debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define deb(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define deb(...) 42
#endif
template<typename T>
struct FenwickTree{
vector<T> bit;
int n;
FenwickTree(int num) : n(num), bit(num, (T)0){
}
T sum(int r){
T ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
T sum(int l, int r){
return sum(r) - sum(l - 1);
}
void update(int idx, T delta){
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
int lower_bound(T val){
int cur = 20, pos = 0;
T sum = 0;
while(cur >= 0){
if((pos + (1 << cur)) < n and (sum + bit[pos + (1 << cur)]) < val) sum += bit[pos + (1 << cur)], pos += (1 << cur);
cur--;
}
return pos + 1;
}
int upper_bound(T val){
return lower_bound(val + ((T)1));
}
};
int up[300000][21];
int depth[3000000];
vector<vector<int>> edges;
int l = 20;
void dfs(int u, int par = -1){
if(par == -1){
depth[u] = 0;
up[u][0] = u;
}
else{
depth[u] = depth[par] + 1;
up[u][0] = par;
}
for(int i = 1; i < l; i++){
up[u][i] = up[up[u][i-1]][i-1];
}
for(auto v : edges[u]){
if(v != par){
dfs(v, u);
}
}
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int dist = depth[u] - depth[v];
for(int i = 0; i < l; i++) if(dist&(1 << i)) u = up[u][i];
if(u == v) return u;
for(int i = l-1; i >= 0; i--){
if(up[u][i] != up[v][i]) u = up[u][i], v = up[v][i];
}
return up[u][0];
}
int dist(int u, int v){
int w = lca(u, v);
return depth[u] + depth[v] - (2 * depth[w]);
}
int get(int u, int len){
for(int i = l - 1; i >= 0; i--) if(len&(1 << i)) u = up[u][i];
return u;
}
vector<int> euler;
int st[400000], en[400000];
ll res[400000];
void dfs2(int u, int par = -1){
st[u] = euler.size();
euler.push_back(u);
for(auto v : edges[u]) {
if(v != par) dfs2(v, u), euler.push_back(u);
}
en[u] = euler.size() - 1;
}
ll bef[500000];
main(){
#ifdef XOX
freopen("D:\\V S Code\\cpp\\competitiveProgramming\\Input.txt", "r", stdin);
freopen("D:\\V S Code\\cpp\\competitiveProgramming\\OPT.txt", "w", stdout);
#endif
ios::sync_with_stdio(!cin.tie(NULL));
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> edge;
edges.resize(n + 10);
int u, v;
for(int i = 1; i < n; i++) {
cin >> u >> v;
edges[u].push_back(v);
edges[v].push_back(u);
edge.push_back({u, v});
}
dfs(1), dfs2(1);
FenwickTree<ll> tree(2*n + 10), tree2(2*n + 10);
memset(bef, 0, sizeof(bef));
bool state[400000];
memset(state, false, sizeof(state));
int ind, cur;
for(int i = 1; i <= n; i++) res[i] = 1;
for(int i = 1; i <= n; i++) tree.update(st[i], 1), tree.update(en[i], -1);
auto findRep = [&] (int u) {
int hi = n, lo = 0, mid;
int v;
while(hi > lo) {
mid = (hi + lo + 1) /2;
v = get(u, mid);
if(tree.sum(st[v], st[u] - 1)) hi = mid - 1;
else lo = mid;
}
return get(u, lo);
};
while(m--) {
cin >> ind;
ind--;
if(depth[edge[ind].first] > depth[edge[ind].second]) swap(edge[ind].first, edge[ind].second);
u = edge[ind].first, v = edge[ind].second;
if(!state[ind]) {
cur = findRep(u);
res[cur] = res[cur] + res[v] - bef[v];
tree.update(st[v] - 1, -1), tree.update(en[v], 1);
deb(cur, st[v] - 1, en[v], v, u, res[cur]);
}
else {
res[v] = res[findRep(v)];
bef[v] = res[findRep(v)];
tree.update(st[v] - 1, 1), tree.update(en[v], -1);
}
state[ind] = !state[ind];
}
while(q--) {
cin >> u;
cout << res[findRep(u)] << "\n";
}
deb(res[findRep(4)]);
}
Compilation message
synchronization.cpp:135:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
synchronization.cpp: In function 'int main()':
synchronization.cpp:190:55: warning: statement has no effect [-Wunused-value]
deb(cur, st[v] - 1, en[v], v, u, res[cur]);
^
synchronization.cpp:205:25: warning: statement has no effect [-Wunused-value]
deb(res[findRep(4)]);
^
synchronization.cpp: In instantiation of 'FenwickTree<T>::FenwickTree(int) [with T = long long int]':
synchronization.cpp:158:34: required from here
synchronization.cpp:37:9: warning: 'FenwickTree<long long int>::n' will be initialized after [-Wreorder]
int n;
^
synchronization.cpp:36:15: warning: 'std::vector<long long int, std::allocator<long long int> > FenwickTree<long long int>::bit' [-Wreorder]
vector<T> bit;
^~~
synchronization.cpp:39:5: warning: when initialized here [-Wreorder]
FenwickTree(int num) : n(num), bit(num, (T)0){
^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4608 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4608 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4608 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4608 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 6 |
Correct |
11 ms |
4864 KB |
Output is correct |
| 7 |
Correct |
38 ms |
7040 KB |
Output is correct |
| 8 |
Correct |
38 ms |
7040 KB |
Output is correct |
| 9 |
Correct |
38 ms |
7040 KB |
Output is correct |
| 10 |
Correct |
552 ms |
27752 KB |
Output is correct |
| 11 |
Correct |
524 ms |
27628 KB |
Output is correct |
| 12 |
Correct |
1141 ms |
32364 KB |
Output is correct |
| 13 |
Correct |
350 ms |
27496 KB |
Output is correct |
| 14 |
Correct |
264 ms |
26980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
27756 KB |
Output is correct |
| 2 |
Correct |
281 ms |
29420 KB |
Output is correct |
| 3 |
Correct |
288 ms |
31728 KB |
Output is correct |
| 4 |
Correct |
271 ms |
31596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 6 |
Correct |
11 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
57 ms |
7552 KB |
Output is correct |
| 8 |
Correct |
1284 ms |
33004 KB |
Output is correct |
| 9 |
Correct |
1301 ms |
32940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1287 ms |
30060 KB |
Output is correct |
| 2 |
Correct |
455 ms |
32680 KB |
Output is correct |
| 3 |
Correct |
456 ms |
32744 KB |
Output is correct |
| 4 |
Correct |
447 ms |
32748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4608 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4608 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 4 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 5 |
Correct |
10 ms |
4864 KB |
Output is correct |
| 6 |
Correct |
48 ms |
7168 KB |
Output is correct |
| 7 |
Correct |
670 ms |
28600 KB |
Output is correct |
| 8 |
Correct |
1304 ms |
33080 KB |
Output is correct |
| 9 |
Correct |
471 ms |
28584 KB |
Output is correct |
| 10 |
Correct |
400 ms |
28268 KB |
Output is correct |
| 11 |
Correct |
433 ms |
30980 KB |
Output is correct |
| 12 |
Correct |
408 ms |
30956 KB |
Output is correct |
| 13 |
Correct |
463 ms |
32880 KB |
Output is correct |
