#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define lli long long
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
#define repv(i, x) for(auto i : x)
#define nl "\n"
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(ii, a, b){ cout << x[ii] << ", "; } cout << "]" << nl
#define MAX_N 100003
lli n, q, a, b, d, raiz, tiempo, hoja, paridad;
vector<int> hijos[MAX_N];
lli tam[MAX_N], hojas[MAX_N], p[MAX_N], hijomayor[MAX_N], visto[MAX_N], hld[MAX_N], hojaextendida[MAX_N];
lli segtree[MAX_N << 1], lazy[MAX_N << 1];
void dfs(lli nodo, lli padre){
p[nodo] = padre;
tam[nodo] = 1; // EL MISMO
if (hijos[nodo].size() == 1) hojas[nodo] = 1;
for(auto h : hijos[nodo]){
if (h == padre) continue;
dfs(h, nodo);
tam[nodo] += tam[h]; // AGREGA AL SUBARBOL DEL PADRE EL TAMAÑO DEL SUBARBOL DEL HIJO
hojas[nodo] += hojas[h]; // AGREGA AL PADRE TODAS LAS HOJAS DEL HIJO
if (hijomayor[nodo] == 0 || tam[h] > tam[hijomayor[nodo]]) hijomayor[nodo] = h; // GUARDA EL HIJO MAYOR PARA EL HLD
}
}
void HLD(lli nodo, lli padre){
if (padre == 0) hld[nodo] = nodo; // SI ES LA RAIZ, ES CABEZA DE SU RAMA DE HLD
visto[nodo] = ++tiempo; // MARCA EL TIEMPO EN QUE VISITASTE ESTE NODO. LA RAIZ SE VE EN EL TIEMPO 1
if (hijomayor[nodo]){
hld[hijomayor[nodo]] = hld[nodo]; // ASIGNA A TU HIJO MAYOR A LA MISMA RAMA QUE TU
HLD(hijomayor[nodo], nodo); // BAJA POR EL HIJO MAYOR, ASUMIENDO QUE EXISTE
}
for(auto h : hijos[nodo]){
if (h == padre || h == hijomayor[nodo]) continue;
hld[h] = h; // CREA UNA NUEVA RAMA PARA CADA HIJO QUE NO ES EL MAYOR.
HLD(h, nodo);
}
}
void push(lli nodo, lli s, lli e){
if (!lazy[nodo]) return; // SI NO HAY NADA QUE HACER SAL.
segtree[nodo] = (e - s + 1) - segtree[nodo]; // CAMBIA LA SUMA DEL NODO AL INVERSO, LOS QUE ANTES SUMABAN AHORA NO Y VICEVERSA
if (s < e){ // SI EL RANGO TIENE HIJOS
lazy[nodo * 2] ^= 1;
lazy[nodo * 2 + 1] ^= 1; // HAZLES TOGGLE A SUS NODOS
}
lazy[nodo] = 0; // LIMPIA EL LAZY
}
void updatest(lli nodo, lli s, lli e, lli l, lli r, lli val){
push(nodo, s, e);
if (s > r || e < l) return;
if (s >= l && e <= r){
lazy[nodo] ^= val;
push(nodo, s, e);
return;
}
// ACTUALIZA AMBOS LADOS
lli mitad = (s + e) / 2;
updatest(nodo * 2, s, mitad, l, r, val);
updatest(nodo * 2 + 1, mitad + 1, e, l, r, val);
// HAZ EL MERGE
segtree[nodo] = segtree[nodo * 2] + segtree[nodo * 2 + 1];
}
void updatehld(lli nodo){
while (nodo > 0){ // MIENTRAS NO LLEGUE A LA RAIZ
// ACTUALIZA EL RANGO DEL SEGMENT TREE QUE VA DEL MOMENTO EN QUE SE VIO EL PADRE DE LA CADENA/RAMA DEL HLD AL QUE PERTENECE HASTA EL NODO QUE SE DESEA ACTUALIZAR.
updatest(1, 1, tiempo, visto[hld[nodo]], visto[nodo], 1);
nodo = p[hld[nodo]]; // MUEVETE AL PADRE DE LA CADENA ACTUAL DEL HLD
}
}
lli getroot(lli nodo, lli s, lli e){
// LA RAZON DE HACER ESTA FUNCION ES QUE SE PROPAGUE CUALQUIER PUSH QUE HUBIERA QUEDADO SUELTO EN EL CAMINO AL NODO 1
push(nodo, s, e);
if (s == 1 && e == 1) return segtree[nodo];
lli mitad = (s + e) / 2;
// VE SOLO AL LADO IZQUIERDO YA QUE SOLO NOS INTERESA EL NODO 1
return getroot(nodo * 2, s, mitad);
}
int main()
{
fastio;
cin >> n >> q;
rep(i, 1, n - 1){
cin >> a >> b;
hijos[a].push_back(b);
hijos[b].push_back(a);
}
// UTILIZA COMO RAIZ UN NODO QUE NO SEA HOJA.
rep(i, 1, n) if(hijos[i].size() > 1){
raiz = i;
break;
}
// HAZ EL PRECALCULO DE TODO EL ARBOL, tam del subarbol (para el HLD), cantidad de hojas en subarbol (para saber su paridad), padre (para poder subir en el HLD)
dfs(raiz, 0);
// DESCOMPON EL ARBOL EN CADENAS CON UN HEAVY-LIGHT DECOMPOSITION
HLD(raiz, 0);
// ACTUALIZA EL SEGMENT TREE DEL ARBOL ORIGINAL CON LAS PARIDADES DE CADA ARBOL, LOS NODOS PARES AGREGAN UNO EXTRA AL COSTO.
rep(i, 1, n) updatest(1, 1, tiempo, visto[i], visto[i], !(hojas[i] & 1));
rep(i, 1, q){
cin >> d;
vector<int> nuevashojas(d, 0);
rep(j, 0, d - 1) cin >> nuevashojas[j];
// AGREGA LAS HOJAS
rep(j, 0, d - 1){
hoja = nuevashojas[j];
if (hijos[hoja].size() == 1 && !(hojaextendida[hoja])){
// ES UNA HOJA PERO ESTE ES SU PRIMER NODO, ENTONCES NO DEBE AFECTAR, PARA HACER MAS SENCILLO EL CODIGO
// SE HARA UNA DOBLE ACTUALIZACION PARA QUE QUEDE IGUAL Y SE MARCA COMO QUE YA SE EXTENDIO
hojaextendida[hoja] = 1;
// ACTUALIZA TODO EL HLD
updatehld(hoja);
}
updatehld(hoja); // ACTUALIZA
}
// CHECA LA RAIZ
paridad = getroot(1, 1, tiempo); // OBTEN LA PARIDAD DE LA RAIZ CON ESTE ARBOL
if (!(paridad & 1)) cout << "-1\n"; // SI EL NODO NO SUMA DOBLE (NO ES PAR) ENTONCES NO SE PUEDE RESOLVER.
else cout << n + d + segtree[1] - 2 << "\n"; // LA RAZON DE RESTAR 2 ES QUE EL TOTAL DE ARISTAS ES (n - 1) Y SE DEBE QUITAR EL EXTRA QUE IRIA DE LA RAIZ A SU PADRE
// QUITA LAS HOJAS
rep(j, 0, d - 1){
hoja = nuevashojas[j];
if (hijos[hoja].size() == 1 && hojaextendida[hoja]){
// QUITA EL DOBLE
hojaextendida[hoja] = 0;
updatehld(hoja);
}
updatehld(hoja);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
418 ms |
6248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
3788 KB |
Output is correct |
| 2 |
Correct |
84 ms |
3788 KB |
Output is correct |
| 3 |
Incorrect |
99 ms |
14272 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
4472 KB |
Output is correct |
| 2 |
Correct |
68 ms |
4488 KB |
Output is correct |
| 3 |
Incorrect |
132 ms |
22896 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
6852 KB |
Output is correct |
| 2 |
Correct |
145 ms |
5856 KB |
Output is correct |
| 3 |
Correct |
20 ms |
5580 KB |
Output is correct |
| 4 |
Correct |
26 ms |
5960 KB |
Output is correct |
| 5 |
Correct |
29 ms |
6332 KB |
Output is correct |
| 6 |
Correct |
131 ms |
6452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
592 ms |
11760 KB |
Output is correct |
| 2 |
Correct |
951 ms |
11684 KB |
Output is correct |
| 3 |
Correct |
758 ms |
7552 KB |
Output is correct |
| 4 |
Correct |
983 ms |
11640 KB |
Output is correct |
| 5 |
Execution timed out |
1008 ms |
11656 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
745 ms |
16772 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
418 ms |
6248 KB |
Output is correct |
| 3 |
Correct |
83 ms |
3788 KB |
Output is correct |
| 4 |
Correct |
84 ms |
3788 KB |
Output is correct |
| 5 |
Incorrect |
99 ms |
14272 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
