As avea si eu o intrebare. Am folosit o tabela de hash in care inserez costurile drumurilor de la radacina (nodul 1) la nodul curent (pe care le inserez pe masura ce fac un DFS), iar inainte sa revin din apelul recursiv al unui DFS, sterg din hash valoarea drumului curent, iar la fiecare pas verific daca exista in hash valoarea drumului curent-S (daca da, inseamna ca exista unul sau mai multe drumuri mai mici pe care daca le exclud din drumul curent voi obtine un drum cu costul S si incrementez solutia cu numarul de aparitii al acelei valori). Totusi, iau 0 puncte, pe 3 teste primesc "Killed by signal 6(SIGABRT).", si pe celelalte 7 primesc "Killed by signal 11(SIGSEGV).". Chiar nu stiu ce poate avea, am reprezentat arborele si hash-ul folosind vectorii din STL. Nu mai stiu ce sa fac, voi posta sursa aici si daca binevoieste cineva sa se uite peste ea, m-as bucura foarte mult. Multumesc anticipat.
#include <iostream>
#include <cstdio>
#include <vector>
#define NMax 1000005
#define U 666013
using namespace std;
vector <int> A[NMax];
vector <int> HT[U+5];
int N, Value[NMax], S, NRoads;
void Read ()
{
freopen ("arbore3.in", "r", stdin);
scanf ("%d %d", &N, &S);
for (int i=1; i<=N; ++i)
{
int F;
scanf ("%d %d", &F, &Value[i]);
A[F].push_back (i);
}
}
void Print ()
{
freopen ("arbore3.out", "w", stdout);
printf ("%d\n", NRoads);
}
int Search (int X)
{
int Key=X%U, NX=0;
for (unsigned i=0; i<HT[Key].size (); ++i)
{
if (HT[Key][i]==X)
{
++NX;
}
}
return NX;
}
void Insert (int X)
{
int Key=X%U;
HT[Key].push_back (X);
}
void Delete (int X)
{
int Key=X%U;
if (HT[Key].size ()==0)
{
return;
}
for (vector <int> :: iterator H=HT[Key].begin (); H!=HT[Key].end (); ++H)
{
if (*H==X)
{
HT[Key].erase (H);
return;
}
}
}
void DFS (int X, int Cost)
{
int C=Cost+Value[X];
NRoads+=Search (C-S);
Insert (C);
for (unsigned V=0; V<A[X].size (); ++V)
{
DFS (A[X][V], C);
}
Delete (C);
}
int main()
{
Read ();
Insert (0);
DFS (1, 0);
Print ();
return 0;
}