#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
// using namespace __gnu_pbds;
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL cout << '\n'
#define dbg(x) cout << #x << " = " << (x) << ' '
#define dbgp(x) cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}
#define epl emplace
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mp make_pair
#define sqr(x) ((x) * (x))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define lwb lower_bound
#define upb upper_bound
#define clz __builtin_clzll // or __builtin_clz
#define ctz __builtin_ctzll // or __builtin_ctz
#define pct __builtin_popcountll // or __builtin_popcount
typedef long long ll;
typedef long double ldb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<int, int> pii;
typedef pair<ldb, ldb> pld;
typedef pair<double, double> pdd;
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
template<class T> void remDup(vector<T> &v){sort(all(v)); v.erase(unique(all(v)),v.end());}
// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 1e5 + 3;
int n, m, q, tin[N], tout[N], timer;
int jmp[N][17], bit[N], f[N], last_del[N];
bool stat[N];
vector<int> adj[N];
pii edge[N];
void dfs(int u, int par){
tin[u] = ++timer;
for(int &v : adj[u]) if(v != par){
jmp[v][0] = u;
for(int i = 1; i < 17; ++i) if(jmp[v][i - 1]){
jmp[v][i] = jmp[jmp[v][i - 1]][i - 1];
}
dfs(v, u);
}
tout[u] = ++timer;
}
void update(int i, int v){
for(; i <= timer; i += i & -i) bit[i] += v;
}
int get_sum(int i){
int res = 0;
for(; i >= 1; i -= i & -i) res += bit[i];
return res;
}
int get_root(int u){
int path_root_u = get_sum(tin[u]);
for(int i = 16; i >= 0; --i) if(jmp[u][i]){
if(path_root_u - (1 << i) == get_sum(tin[jmp[u][i]])) u = jmp[u][i];
}
return (get_sum(tin[jmp[u][0]]) == get_sum(tin[u]) ? u : jmp[u][0]);
}
void TS_2392(){
cin >> n >> m >> q;
for(int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
edge[i] = {u, v};
adj[u].eb(v); adj[v].eb(u);
}
dfs(1, 0);
for(int i = 1; i < n; ++i){
if(jmp[edge[i].fi][0] == edge[i].se) swap(edge[i].fi, edge[i].se);
}
fill(f + 1, f + 1 + n, 1);
while(m--){
int id, u, v, root_u; cin >> id;
tie(u, v) = edge[id]; root_u = get_root(u);
if(stat[id] == 0){
f[root_u] = f[root_u] + f[v] - last_del[v];
update(tin[v], 1); update(tout[v], -1);
}
else{
last_del[v] = f[v] = f[root_u];
update(tin[v], -1); update(tout[v], 1);
}
stat[id] = !stat[id];
//dbg(root_u); dbg(u); dbg(v); dbg(f[root_u]); dbg(f[v]); EL;
}
while(q--){
int u; cin >> u;
//dbg(u); dbg(get_root(u));
cout << f[get_root(u)] << '\n';
}
}
int main(){
SPEED; fileIO("text");
int numtest = 1; // cin >> numtest;
for(int itest = 1; itest <= numtest; ++itest){
// cout << "Case #" << itest << ": ";
TS_2392(); // cout << '\n';
}
return 0;
}
/* stuff you should look for
* int overflow, array bounds
* small cases, special cases (n = 1 ???)
* do something instead of nothing: code bruteforce
* WRITE STUFF DOWN and STAY ORGANIZED
* DON'T GET STUCK ON ONE APPROACH
*/
Compilation message
synchronization.cpp: In function 'int main()':
synchronization.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:118:12: note: in expansion of macro 'fileIO'
118 | SPEED; fileIO("text");
| ^~~~~~
synchronization.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:118:12: note: in expansion of macro 'fileIO'
118 | SPEED; fileIO("text");
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6628 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6580 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Correct |
10 ms |
7556 KB |
Output is correct |
| 8 |
Correct |
8 ms |
7256 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7516 KB |
Output is correct |
| 10 |
Correct |
90 ms |
17804 KB |
Output is correct |
| 11 |
Incorrect |
92 ms |
17672 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
20768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6616 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
6488 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
24720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
