/*
thisiscaau's code
trying my best for a better future
*/
#include <bits/stdc++.h>
#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define endl '\n'
typedef pair<ll,ll> ii;
ll const mod = 1e9 + 7, MAXN = 2e5 + 5,oo = 3e18;
class fenwick {
private : vector<ll> ft;
public :
fenwick (ll n){
ft.assign(n + 5,0);
}
ll ls (ll x){
return x & (-x);
}
ll rsq (ll pos){
if (pos == 0) return 0;
ll res = 0;
for ( ; pos ; pos -= ls(pos)){
res += ft[pos];
}
return res;
}
void inc (ll pos,ll val){
for ( ; pos < ft.size() ; pos += ls(pos)){
ft[pos] += val;
}
}
};
fenwick ft(MAXN);
// difference array
ll tc,n,m,q,now = 1;
vector<ll> g[MAXN];
ll tin[MAXN],tout[MAXN],save[MAXN];
ll dep[MAXN];
ll sz[MAXN];
ll up[MAXN][20];
bool rem[MAXN];
vector<ii> edges;
void dfs (ll u,ll p = 0){
tin[u] = now++;
up[u][0] = p;
sz[u] = 1;
for (int i = 1 ; i < 20 ; i++){
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (ll v : g[u]){
if (v == p) continue;
dep[v] = dep[u] + 1;
dfs(v,u);
}
tout[u] = now;
}
ll find_root (ll u){
// find root of u
for (int i = 19 ; i >= 0 ; i--){
if (up[u][i]){
ll path_to_anc = ft.rsq(tin[up[u][i]]);
ll path_to_node = ft.rsq(tin[u]);
ll dist = dep[u] - dep[up[u][i]];
if (path_to_anc + dist == path_to_node){
u = up[u][i];
}
}
}
return u;
}
void aurelion_sol(){
// solution goes here
cin >> n >> m >> q;
for (int i = 1 ; i < n ; i++){
ll u,v; cin >> u >> v;
g[u].pb(v); g[v].pb(u);
edges.pb(mp(u,v));
}
dfs(1);
for (auto &cur : edges){
if (up[cur.fi][0] == cur.se) {
swap(cur.fi,cur.se);
}
}
for (int i = 1 ; i <= m ; i++){
ll edge_id; cin >> edge_id;
ii cur = edges[edge_id - 1];
if (!rem[edge_id]){
// add edge
ll root = find_root(cur.fi);
sz[cur.fi] += sz[cur.se] - save[edge_id];
ft.inc(tin[cur.se],1);
ft.inc(tout[cur.se],-1);
}
else {
// remove edge
save[edge_id] = sz[cur.se] = sz[find_root(cur.fi)];
ft.inc(tin[cur.se],-1);
ft.inc(tout[cur.se],1);
}
rem[edge_id] = !rem[edge_id];
}
for (int i = 1 ; i <= q ; i++){
ll node; cin >> node;
cout << sz[find_root(node)] << endl;
}
}
signed main() {
#ifdef thisiscaau
fileopen("input", "output");
#endif
#ifndef thisiscaau
// fileopen1("LAH");
#endif
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
tc = 1;
while (tc--) aurelion_sol();
}
Compilation message
synchronization.cpp: In member function 'void fenwick::inc(long long int, long long int)':
synchronization.cpp:41:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for ( ; pos < ft.size() ; pos += ls(pos)){
| ~~~~^~~~~~~~~~~
synchronization.cpp: In function 'void aurelion_sol()':
synchronization.cpp:111:7: warning: unused variable 'root' [-Wunused-variable]
111 | ll root = find_root(cur.fi);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
6604 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6604 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
6588 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
35012 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
6596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
271 ms |
38708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
6604 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
6604 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
