#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;
auto add = [&](int l, int r, ll x) {
tree.update(l, x), tree.update(r + 1, -x);
tree2.update(l, -x*(l - 1)), tree2.update(r + 1, x*r);
};
auto val = [&](ll l) {
return tree.sum(l) * l + tree2.sum(l);
};
auto rval = [&](ll l, ll r) {
return val(r) - val(l - 1);
};
for(int i = 1; i <= n; i++) add(st[i], st[i], 1), add(en[i], en[i], -1);
auto findRep = [&](int u) {
int hi = n, lo = 0, v, mid;
while(hi > lo) {
mid = (hi + lo + 1) / 2;
v = get(u, mid);
if(rval(st[v], st[u] - 1)) {
hi = mid - 1;
}
else lo = mid;
}
v = get(u, lo);
return v;
};
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];
bef[v] = res[v];
add(st[v] - 1, st[v] - 1, -1), add(en[v], en[v], 1);
deb(cur, res[cur], u, v, bef[v], findRep(v), rval(st[v], st[v]));
}
else {
res[v] = res[findRep(u)];
add(st[v] - 1, st[v] - 1, 1), add(en[v], en[v], -1);
}
state[ind] = !state[ind];
}
int hi, lo, mid;
while(q--) {
cin >> u;
v = findRep(u);
cout << res[v] << "\n";
}
for(int i = 0; i <= 2*n + 1; i++) cerr << rval(i, i) << " ";
cerr << "\n";
deb(findRep(4), tree.sum(st[2], st[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:205:77: warning: statement has no effect [-Wunused-value]
deb(cur, res[cur], u, v, bef[v], findRep(v), rval(st[v], st[v]));
^
synchronization.cpp:224:44: warning: statement has no effect [-Wunused-value]
deb(findRep(4), tree.sum(st[2], st[4]));
^
synchronization.cpp:214:9: warning: unused variable 'hi' [-Wunused-variable]
int hi, lo, mid;
^~
synchronization.cpp:214:13: warning: unused variable 'lo' [-Wunused-variable]
int hi, lo, mid;
^~
synchronization.cpp:214:17: warning: unused variable 'mid' [-Wunused-variable]
int hi, lo, mid;
^~~
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 |
Incorrect |
7 ms |
4736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1149 ms |
30224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
4736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2430 ms |
33440 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4736 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
4736 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
