Salve a tutti, oggi stavo provando a risolvere in maniera molto rustica il problema fire on a tree, l’attuale codice che sto usando, risolve entrambi gli esempi in un tempo anche abbastanza ragionevole, ero già consapevole che sarebbe andato out of time nella subtask 4, volevo capire però per quale ragione non riuscisse nemmeno a risolvere le subtask precedenti dove l’input è abbastanza piccolo, ringrazio in anticipo, buona giornata.
#include <iostream>
#include <fstream>
#include <vector>
struct Edge {
int des;
};
std::vector<std::vector<Edge>> edges;
long long int dfs(int s, int starting, bool firstCall)
{
long long int tot = edges[s].size();
long long int max = 1;
if (tot <= 1)
{
if(!firstCall)
{
return 0;
}
else
{
return 1;
}
}
if(firstCall)
{
max = 0;
}
else
{
max++;
}
int previous = 0;
for(auto u: edges[s])
{
if(u.des!=starting)
{
previous = dfs(u.des,s,false);
tot = tot + previous;
if(previous>max)
{
max = previous;
}
}
}
return tot - max;
}
long long int dfs(int s, int starting, bool firstCall);
int main() {
int N;
std::ifstream cin("input.txt");
std::ofstream cout("output.txt");
cin >> N;
edges.resize(N);
int a = 0;
for ( int i = 0; i < N-1; ++i)
{
int src;
cin >> a;
Edge edge;
src = a;
cin >> edge.des;
edges[src].push_back(edge);
Edge ede;
src = edge.des;
ede.des = a;
edges[src].push_back(ede);
}
for(int i = 0; i < N; i++)
{
cout << dfs(i,i,true) << " ";
}
cout << std::endl;
return 0;
}