Оптимизация DFS. Перебор всех вершин графа.

Есть такая задача:
Дан связный неориентированный невзвешенный граф на n вершинах и n-1 ребре. (Попросту говоря дерево). И есть игрок который перемещается между зданием 1 и зданием 2 (здания = вершины) наикратчайшим путём. При прохождении некоторых рёбер на игрока накладываются негативные эффекты (поштучно, 1 за ребро), и, если негативных эффектов суммарно стало k или больше, игрок умирает. Помогите разработчикам по заданным n, k и информации о рёбрах посчитать общее количество способов расставить здания 1 и 2, чтобы игрок не умер.

Входные данные:
В первой строке записаны числа n и k. (1 <= n <= 10^5 (10 в степени 5), 0 <= k <= 2^15).
В следующих n-1 строках записаны числа u_{i}, v_{i}, b_{i} (1 <= u, v <= n, u != v, 0 <= b <= 1) которые означают существование ребра между вершинами u_{i} и v_{i}. Если b = 1, то на этом ребре игрок получает негативный эффект. (1 штука)

Выходные данные:
Выведите одно число - количество способов выбрать здание 1 и здание 2 так, чтобы игрок не умер.

Ограничение по времени: 2000 мс
Ограничение по памяти: 256 мб

Моё решение основывается на том, что DFS рано или поздно обойдёт все вершины, так как естественных ограничений этому нет, а значит мы можем ограничить его по k. Тогда решение таково, что сколько вершин DFS успел посетить до того, как умер, это количество способов для вершины i. Запустимся от всех -- получим общее количество способов.

Вот код:

 #include <iostream> 
#include <vector> 
using namespace std; 
 
const int MAXN = 100005; 
vector<pair<int, int>> graph[MAXN];  
int n, k; 
long long result = 0; 
 
void dfs(int vertex, int parent, int apathy) { 
    for (auto &edge: graph[vertex]) { 
        int nextVertex = edge.first; 
        int road = edge.second; 
 
        if (nextVertex == parent) continue; 
 
        int nextApathy = apathy + (road == 1 ? 1 : 0); 
         
        if (nextApathy <= k) { 
            result++; 
            dfs(nextVertex, vertex, nextApathy); 
        } 
    } 
} 
 
int main() { 
    cin >> n >> k; 
     
    for (int i = 0; i < n - 1; ++i) { 
        int u, v, b; 
        cin >> u >> v >> b; 
        u--; v--;  
        graph[u].push_back({v, b}); 
        graph[v].push_back({u, b}); 
    } 
     
    for (int i = 0; i < n; ++i) { 
        dfs(i, -1, 0); 
    } 
    cout << result << '\n'; 
    return 0; 
}  

Он решает задачу, но он не проходит по времени. Помогите, пожалуйста, оптимизировать. Прагмы в задаче запрещены, пробовал.