Fire on a tree (fire) 60/100

Aiuto
1

Ciao, stavo provando a risolvere il problema Fire on a tree (fire) ma ottengo 60/100 perché nell’ultima subtask 3 testcase vanno in TLE. Mi domandavo se il problema riguardasse il mio approccio di memoization o se devo cambiare copletamente l’idea di fondo.
Condivido il mio codice:

#include <bits/stdc++.h>
using namespace std;

// Funzione di hash personalizzata per pair<int, int>
struct hash_pair {
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const {
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        return hash1 ^ hash2;  
    }
};

int f(int nodo, int from, const vector<vector<int>>& graph, unordered_map<pair<int, int>, int, hash_pair>& memo) {
    if (graph[nodo].size() == 1 || (graph[nodo].size() == 2 && from != -1)) return 1;

    pair<int, int> key = {nodo, from};

    if (from != -1 && memo.find(key) != memo.end()) return memo[key];

    int maxx = -1;
    int summ = 0;
    for (const int son : graph[nodo]) {
        if (son != from) {
            int x = f(son, nodo, graph, memo);
            maxx = max(maxx, x);
            summ += x;
        }
    }

    int result = (summ - maxx) + 1;

    if (from != -1) memo[key] = result;

    return result;
}

static const int _ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

int main() {
    // Uncomment the following lines if you want to read/write from files
    ifstream cin("input.txt");
    ofstream cout("output.txt");

    int N;
    cin >> N;
    vector<vector<int>> graph(N);
    unordered_map<pair<int, int>, int, hash_pair> memo;  

    for (int i = 0; i < N - 1; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for (int i = 0; i < N; i++) {
        cout << f(i, -1, graph, memo) << " ";
    }

    return 0;
}

Grazie in anticipo.

2

Ciao. La tua soluzione mi sembra quadratica. Anche se memorizzi gli stati, se sono N² la soluzione è comunque quadratica. Prova a pensare a come sfruttare meglio le informazioni di una sola DFS per calcolare anche gli altri nodi.
Spoiler, la tecnica è rerooting

3

Ciao, grazie. Effettivamente avevo il dubbio che fosse quadratica. Riguardo al rerooting non lo conosco, ora cerco di che si tratta e provo a risolvere.