#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
typedef complex<int> point;
const int MAX_N = 100000;
vector<vector<int>> adj;
vector<int> parity;
vector<int> anc;
vector<int> cost = {2, 1};
vector<pii> above_it;
int total_cost= 0;
int count_leaves(int u, int a){
int s= 0;
for(auto v: adj[u]){
if(v!=a){
anc[v] = u;
s+=count_leaves(v, u);
}
}
if(s==0){
s=1;
}
total_cost+= cost[s%2];
//cout<<u+1<<" "<<s<<endl;
parity[u] = s%2;
return s;
}
void mark_nodes(int u, pii cur, int a){
if(parity[u] == 0){
cur.first++;
}
else{
cur.second++;
}
above_it[u] = cur;
for(auto v: adj[u]){
if(v!=a){
mark_nodes(v, cur, u);
}
}
}
void flip(int u){
//cout<<"flip "<<u+1<<endl;
total_cost -= cost[parity[u]];
parity[u] ^= 1;
total_cost+=cost[parity[u]];
if(anc[u]!=-1){
flip(anc[u]);
}
}
signed main(){
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int n, k;
cin>>n>>k;
adj.resize(n);
parity.resize(n);
anc.resize(n, -1);
above_it.resize(n, {0, 0});
int node = 0;
int deg= 0;
for(int i = 0; i<n-1; i++){
int a, b;
cin>>a>>b;
a--;b--;
adj[a].push_back(b);
adj[b].push_back(a);
if(adj[a].size()>deg){
node =a;
deg = adj[a].size();
}
if(adj[b].size()>deg){
node =b;
deg = adj[b].size();
}
}
int r=count_leaves(node, -1);
//cout<<"base "<<total_cost<<endl;
mark_nodes(node, {0, 0}, -1);
for(int i = 0; i<k; i++){
int d;
cin>>d;
int changed;
cin>>changed;
changed--;
total_cost++;
if(adj[changed].size()>1){
total_cost -= above_it[changed].first;
total_cost+=above_it[changed].second;
parity[node]^=1;
}
if(parity[node]==1){
cout<<-1<<endl;
}
else{
cout<<total_cost-2<<endl;
}
if(adj[changed].size()>1){
total_cost += above_it[changed].first;
total_cost-=above_it[changed].second;
parity[node]^=1;
}
total_cost--;
}
}
Compilation message
cleaning.cpp: In function 'int main()':
cleaning.cpp:75:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
75 | if(adj[a].size()>deg){
| ~~~~~~~~~~~~~^~~~
cleaning.cpp:79:25: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
79 | if(adj[b].size()>deg){
| ~~~~~~~~~~~~~^~~~
cleaning.cpp:86:9: warning: unused variable 'r' [-Wunused-variable]
86 | int r=count_leaves(node, -1);
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
1112 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
3412 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
7924 KB |
Output is correct |
2 |
Incorrect |
28 ms |
7516 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
11344 KB |
Output is correct |
2 |
Correct |
188 ms |
15176 KB |
Output is correct |
3 |
Correct |
163 ms |
14788 KB |
Output is correct |
4 |
Correct |
161 ms |
13668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |