This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
vector<ll> edges[200005];
vector<ll> vtree[200005];
ll realans = 0;
ll vals[200005];
ll contrib[200005];
ll depth[200005];
ll par[200005];
ll tin[200005];
ll timer = 0;
map<ll, ll> lmao;
ll lmfao = 0;
int dp(ll a, ll p){
tin[a] = timer++;
par[a] = p;
ll ans = 0;
if (edges[a].size() <= 1) ans = 1;
for (auto&i : edges[a]){
if (i != p) ans += dp(i, a);
}
if (p!=-1) realans += 1 + (ans+1)%2;
if (p != -1) vals[a] = 1 + (ans+1)%2;
return 1 + (ans+1)%2;
}
void dp2(ll a, ll p, ll d){
depth[a] = d;
if (p==-1) contrib[a] = 0;
if (p != -1){
contrib[a] = contrib[par[a]] + vals[a];
}
for (auto&i : edges[a]){
if (i != p) dp2(i, a, d+1);
}
}
ll dp3(ll a, ll p){
ll tot = lmao[a];
for (auto&i : vtree[a]) if (i != p) tot += dp3(i, a);
lmfao += (tot/2)*2 * -(depth[a]*3 - contrib[a]*2);
return tot;
}
int anc[200005][30];
int ancc(ll a, ll x){
if (par[a] == -1) return a;
if (x==0) return par[a];
if (anc[a][x] != -1) return anc[a][x];
else{
return anc[a][x] = ancc(ancc(a,x-1),x-1);
}
}
int lca(ll a, ll b){
if (depth[a] < depth[b]) swap(a,b);
FORNEG(i,29,-1) if (depth[ancc(a, i)] >= depth[b]) a = ancc(a,i);
if (a==b) return a;
FORNEG(i,29,-1) if (ancc(a,i) != ancc(b,i)) a = ancc(a,i), b = ancc(b,i);
return par[a];
}
int main(){
FOR(i,0,200005) FOR(j,0,30) anc[i][j] = -1;
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,q;
cin >> n >> q;
FOR(i,0,n-1){
ll a,b;
cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
ll root = -1;
ll cnt = 0;
FOR(j,1,n+1){
if (edges[j].size() != 1){
root = j;
}else{
cnt++;
}
}
dp(root, -1);
dp2(root, -1, 0);
ll ans = 0;
FOR(i,1,n+1) ans += vals[i];
FOR(i,0,q){
ll d; cin >> d;
ll cur = n+1;
ll curans = 0;
set<ll> used;
ll newleaves=0;
lmao.clear();
vector<vector<ll>> stuff;
lmfao = 0;
FOR(k,0,d){
ll temp; cin >> temp;
used.insert(temp);
curans++;
if (edges[temp].size() == 1)continue;
newleaves++;
stuff.push_back({tin[temp], temp});
curans += depth[temp]*3 - contrib[temp]*2;
lmao[temp] += 1;
}
sort(stuff.begin(), stuff.end());
set<vector<ll>> stuff2;
FOR(i,1,stuff.size()){
ll lcatemp = lca(stuff[i][1], stuff[i-1][1]);
stuff2.insert({tin[lcatemp], lcatemp});
}
if (stuff.size()){
ll lcatemp = lca(stuff[0][1], stuff[stuff.size()-1][1]);
stuff2.insert({tin[lcatemp], lcatemp});
}
for (auto&i : stuff)stuff2.insert(i);
vector<ll> stack;
for (auto&k : stuff2){
while (stack.size() && lca(stack[stack.size()-1], k[1]) != stack[stack.size()-1]) stack.pop_back();
if (stack.size()) vtree[stack[stack.size()-1]].push_back(k[1]);
stack.push_back(k[1]);
}
for (auto&k : stuff2){
if (vtree[k[1]].size() != 0){
dp3(k[1], -1);
break;
}
}
if ((cnt+newleaves)%2==1) cout << -1 << "\n";
else{
cout << ans+curans+lmfao << "\n";
}
for (auto&i : stuff) vtree[i[1]].clear();
for (auto&i : used){
while (edges[i].size() && edges[i][edges[i].size()-1]>n){
edges[i].pop_back();
}
}
}
}
Compilation message (stderr)
cleaning.cpp: In function 'int main()':
cleaning.cpp:4:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
144 | FOR(i,1,stuff.size()){
| ~~~~~~~~~~~~~~~~
cleaning.cpp:144:9: note: in expansion of macro 'FOR'
144 | FOR(i,1,stuff.size()){
| ^~~
cleaning.cpp:123:12: warning: unused variable 'cur' [-Wunused-variable]
123 | ll cur = n+1;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |