#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 MOD 1000000007
#define MAX_N 1003
#define perdedor 0
#define ganador 1
lli n, d, a, b, tipo[MAX_N], tipooriginal[MAX_N], critico[MAX_N], cntcriticos, totg, totp;
vector<lli> hijos[MAX_N];
lli binexp(lli b, lli e){
lli res = 1;
while (e > 0){
if (e & 1) res = (res * b) % MOD;
e >>= 1;
b = (b * b) % MOD;
}
return res;
}
lli dfs(lli nodo, lli padre){
lli t = 1;
repv(h, hijos[nodo]){
if (h == padre) continue;
t *= dfs(h, nodo);
}
if (t) return tipooriginal[nodo] = perdedor;
else return tipooriginal[nodo] = ganador;
}
void dfstipos(lli nodo, lli padre, lli tipopadre){
// SI YO SOY GANADOR, SEGUIRE SIENDO GANADOR SIN IMPORTAR LO QUE PASE, YA QUE TENGO AL MENOS UN PERDEDOR EN MI SUBARBOL
if (tipooriginal[nodo] == ganador) tipo[nodo] = ganador;
else{
// SI YO SOY PERDEDOR TODOS MIS HIJOS SON GANADORES, SI EL QUE VIENE DE LA RAIZ ES PERDEDOR YO ME VUELVO GANADOR, DE OTRA FORMA SIGO SIENDO PERDEDOR.
if (tipopadre == perdedor) tipo[nodo] = ganador;
else tipo[nodo] = perdedor;
}
repv(h, hijos[nodo]){
if (h == padre) continue;
if (nodo == 1){
if (hijos[nodo].size() == 1) dfstipos(h, nodo, perdedor); // SI LA RAIZ ES UNA HOJA ENTONCES ES PERDEDORA
else{
// SI LA RAIZ NO ES UNA HOJA, EL QUE SE VEA COMO HIJO PERDEDOR O GANADOR DEPENDE DE LOS OTROS HIJOS.
lli tp = ganador;
repv(otro, hijos[nodo]){
if (otro == h) continue; // NO TOMES EN CUENTA EL HIJO ACTUAL.
tp *= tipooriginal[otro];
}
if (tp == ganador) dfstipos(h, nodo, perdedor);
else dfstipos(h, nodo, ganador);
}
}
else{
// SI NO ES LA RAIZ, DEPENDE DE SUS HIJOS Y EL PADRE, SI
// EN EL TIPO ORIGINAL ERA GANADOR, SIGNIFICA QUE EN SU SUBARBOL HAY AL MENOS 1 PERDEDOR, POR LO QUE ES GANADOR
// SI EN EL TIPO ORIGINAL ERA PERDEDOR, TODOS SON GANADORES Y DEPENDE DEL TIPO DE SU PADRE.
if (tipooriginal[nodo] == ganador) dfstipos(h, nodo, ganador);
else if (tipopadre == ganador) dfstipos(h, nodo, perdedor);
else dfstipos(h, nodo, ganador);
}
}
}
void dfscriticos(lli nodo, lli padre){
lli cnt = 0;
repv(h, hijos[nodo]){
if (h == padre) continue;
if (tipooriginal[h] == perdedor) ++cnt;
}
if (cnt > 1) return; // SI TIENE MAS DE UN HIJO PERDEDOR, NADIE EN SU SUBARBOL PUEDE SER CRITICO
if (tipooriginal[nodo] == perdedor){
// SI ES UN NODO PERDEDOR Y LA BUSQUEDA LLEGO A EL, SIGNIFICA QUE EN SU CAMINO A LA RAIZ
// NO HAY NINGUN GANADOR CON MAS DE UN HIJO PERDEDOR, POR LO QUE UN CAMBIO EN ESTE NODO
// IMPLICA QUE SE PROPAGA HASTA LA RAIZ.
critico[nodo] = 1;
++cntcriticos;
}
repv(h, hijos[nodo]){
if (h == padre) continue;
if (tipooriginal[nodo] == perdedor || (tipooriginal[nodo] == ganador && tipooriginal[h] == perdedor)) dfscriticos(h, nodo);
}
}
int main()
{
fastio;
cin >> n >> d;
if (n == 2){ cout << binexp(4, d); return 0; }
else if (n > 1000) return 0;
rep(i, 1, n - 1){
cin >> a >> b;
hijos[a].push_back(b);
hijos[b].push_back(a);
}
// VERIFICA DE QUE TIPO ES CADA NODO
tipo[1] = dfs(1, 0);
dfstipos(1, 0, ganador);
// CUENTA LOS PUNTOS QUE SON CRITICOS.
// LOS PUNTOS CRITICOS SON LOS NODOS PERDEDORES QUE EN SU CAMINO A LA RAIZ NO TIENEN NINGUN NODO GANADOR CON DOS O MAS HIJOS PERDEDORES,
// ES DECIR, SI ELLOS CAMBIAN A GANADOR LOS NODOS EN SU CAMINO A LA RAIZ TAMBIEN CAMBIARAN HACIENDO POR TANTO CAMBIAR A LA RAIZ
dfscriticos(1, 0);
// LOS NODOS QUE PUEDEN CAMBIAR EL RESULTADO SON LOS NODOS CRITICOS. EN ESOS NODOS SI SE CONECTA A UN PERDEDOR DEL OTRO LADO CAMBIARA EL VALOR DE LA RAIZ
// ENTONCES...
// SI LA RAIZ ES GANADORA, TODOS LOS NODOS CRITICOS NO DEBEN CONECTARSE A PERDEDORES Y CUALQUIER OTRO NO IMPORTA, EL TOTAL ES ((n - cntcriticos) * n) + (cntcriticos * ganadores)
// SI LA RAIZ ES PERDEDORA, SOLO CAMBIA CONECTANDO LOS CRITICOS A LOS PERDEDORES, EL TOTAL ES (criticos * perdedores)
rep(i, 1, n) if (tipo[i] == perdedor) ++totp;
totg = n - totp;
if (tipooriginal[1] == ganador) cout << ((n * n) - (cntcriticos * totp)) % MOD;
else cout << (cntcriticos * totp) % MOD;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
