#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 100000
lli n,a,b,raiz,q,total, x;
lli res[MAX+2],hojas[MAX+2],paridad[MAX+2];
vector<lli> hijos[MAX+2];
map<lli,lli> mapa[MAX+2];
void ch(lli pos, lli padre) {
if (hijos[pos].size() == 1) hojas[padre]++;
for (auto h : hijos[pos]) {
if (h == padre) continue;
ch(h,pos);
hojas[pos] += hojas[h];
}
}
void DFS (lli pos, lli padre) {
lli query, cant;
for (auto h : hijos[pos]) {
if (h == padre) continue;
// BAJA PRIMERO A TODOS TUS HIJOS
DFS(h,pos);
// HAY QUE HACER UN SMALL-TO-LARGE
if (mapa[pos].size() < mapa[h].size()) swap(mapa[pos], mapa[h]);
for (auto act : mapa[h]) {
query = act.first;
cant = act.second;
// SI EN AMBOS MAPAS ESTA AFECTADO ESE QUERY, HAY QUE VER SI SE CANCELAN,
// SE CANCELAN SI ESTA EN AMBOS Y LA SUMA DE AMBOS ES PAR
if (mapa[pos].find(query) != mapa[pos].end()){
mapa[pos][query] += cant;
if (!(mapa[pos][query] % 2)) mapa[pos].erase(query);
else mapa[pos][query] %= 2;
}
else mapa[pos][query] += cant; // SI NO ESTA EN EL MAPA DEL NODO, AGREGALO
}
}
if (hijos[pos].size() == 1){
vector<int> paraborrar;
// SI EL NODO ES UNA HOJA, AFECTA EL COSTO SI TIENE UN NUMERO PAR DE AGREGADOS
for (auto act : mapa[pos]){
query = act.first;
cant = act.second;
if (cant == 1) paraborrar.push_back(query); // SI LA CANTIDAD DE NODOS ES IMPAR NO SE AFECTA EL COSTO, BORRA LA ENTRADA
else if (cant == 2) res[query]++; // AUMENTA EN 1 EL COSTO PARA ESE QUERY
}
for(auto b : paraborrar) mapa[pos].erase(b);
}
else if (pos == raiz){
// SI EL NODO ES LA RAIZ ENTONCES DEBE SER INVALIDO EN TODOS LOS CASOS EN DONDE LA PARIDAD SEA IMPAR
for (auto act : mapa[pos]){
query = act.first;
cant = act.second;
if (cant == 1 && paridad[raiz] == 0) res[query] = -1;
else if (cant == 2 && paridad[raiz] == 0) res[query] = -1;
}
if (paridad[raiz] == 1){
rep(i, 1, q) if (mapa[raiz].find(i) == mapa[raiz].end()) res[i] = -1;
}
}
else{
// SI EL NODO NO ES HOJA, DEBE AFECTAR EL COSTO EN TODOS LOS QUERYS DONDE TENGA HIJOS,
for (auto act : mapa[pos]){
query = act.first;
cant = act.second;
if (cant == 1 && paridad[pos] == 1) res[query]++; // SI EL NODO ERA IMPAR Y HAY UN NUEVO HIJO, SE VUELVE PAR Y AUMENTA EL COSTO
else if (cant == 1 && paridad[pos] == 0) res[query]--; // SI ERA PAR Y SE LE AGREGA UNO, SE VUELE IMPAR Y DISMINUYE EL COSTO
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
raiz = -1;
rep(i,1,n-1) {
cin >> a >> b;
hijos[a].push_back(b);
hijos[b].push_back(a);
if (raiz == -1) {
if (hijos[a].size() > 1) raiz = a;
if (hijos[b].size() > 1) raiz = b;
}
}
// CUENTA EL NUMERO DE HOJAS EN CADA SUBARBOL
ch(raiz, 0);
// CALCULA UNA PARIDAD PARA CADA NODO, LOS NODOS CON PARIDAD PAR TENDRAN QUE LIMPIAR DOBLE SU ARISTA PADRE
rep (i,1,n) {
if (raiz == i){
if (hojas[i] & 1) paridad[raiz] = 1;
else paridad[raiz] = 0;
continue; // LA RAIZ NO IMPORTA SU PARIDAD PORQUE NO TIENE UN PADRE A QUIEN SUBIR
}
if (hojas[i] == 0 || (hojas[i]&1)) paridad[i] = 1; // SE CONSIDERA QUE LAS HOJAS TIENEN PARIDAD IMPAR
else {paridad[i] = 0; total++;}
}
rep(i,1,q) {
// LEE TODOS LOS QUERIES EN SIMULTANEO
cin >> x;
// INICIALIZA EL RESULTADO INICIAL DE CADA QUERY AL COSTO DEL ARBOL MAS LAS ARISTAS QUE SE ESTAN AGREGANDO
res[i] = n - 1 + total + x;
rep(j,1,x) {
cin >> a;
// SI A UN QUERY NO-HOJA SE LE AGREGA UN NUMERO PAR DE NODOS, ESTOS SE CANCELAN ENTRE ELLOS Y NO CAMBIO EL RESTO DEL ARBOL
if (mapa[a].find(i) != mapa[a].end() && hijos[a].size() > 1) mapa[a].erase(i);
else {
if (hijos[a].size() > 1) mapa[a][i]++; // SI NO ES HOJA, AGREGALE EL NODO EN EL QUERY CORRESPONDIENTE
else{
// SI ES UNA HOJA ENTONCES NO SE PUEDEN CANCELAR LOS PRIMEROS DOS NODOS
mapa[a][i]++;
if (mapa[a][i] > 2) mapa[a][i] -= 2;
}
}
}
}
DFS(raiz, 0);
rep(i, 1, q) cout << res[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7368 KB |
Output is correct |
| 2 |
Incorrect |
165 ms |
16584 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
8108 KB |
Output is correct |
| 2 |
Correct |
24 ms |
8076 KB |
Output is correct |
| 3 |
Correct |
65 ms |
13112 KB |
Output is correct |
| 4 |
Correct |
91 ms |
14780 KB |
Output is correct |
| 5 |
Correct |
109 ms |
16980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
8680 KB |
Output is correct |
| 2 |
Correct |
25 ms |
8840 KB |
Output is correct |
| 3 |
Correct |
102 ms |
21636 KB |
Output is correct |
| 4 |
Correct |
152 ms |
25572 KB |
Output is correct |
| 5 |
Correct |
97 ms |
26520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
12252 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
28648 KB |
Output is correct |
| 2 |
Incorrect |
206 ms |
22836 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
334 ms |
33720 KB |
Output is correct |
| 2 |
Execution timed out |
1091 ms |
24252 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7368 KB |
Output is correct |
| 2 |
Incorrect |
165 ms |
16584 KB |
Output isn't correct |
