Number of routes

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

struct Edge
{
    public:
    int from;
    int to;
    int weight;
    int id;

    Edge(int f, int t, int w, int id)
    {
        this -> from = f;
        this->to = t;
        this->weight = w;
        this->id = id;
    }
};

void MaxEdgeSearch(vector<vector<Edge * >> & gr, int v, vector<bool> & usedEdges, vector<bool> & usedVertex, Edge * & maxEdge)
{
    usedVertex[v] = true;

    for (Edge * edge : gr[v])
    {
        int u = (v == edge -> from ? edge -> to : edge -> from);
        if ( usedVertex[u] == true || usedEdges[ edge -> id ]) //boundary of graph reached
        {
            continue;
        }

        if (maxEdge == NULL)
        {
            maxEdge = edge;
        }
        else
        {
            if (edge -> weight > maxEdge -> weight)
            {
                maxEdge = edge;
            }
        }

        MaxEdgeSearch(gr, u, usedEdges, usedVertex, maxEdge);
    }
}

void CalculateDistance(vector<vector<Edge * >> & gr, int v, map<int, int> & dist, vector<bool> & usedEdges, vector<bool> & usedVertex, map<int, int> & routesPerDistance)
{
    usedVertex[v] = false;

    for (Edge * edge : gr[v])
    {
        int u = (v == edge -> from ? edge -> to : edge -> from);
        if ( usedVertex[u] == false || usedEdges[ edge -> id ])  //boundary of graph reached
        {
            continue;
        }

        dist[u] = dist[v] + 1;
        routesPerDistance[dist[u]]++;
        CalculateDistance(gr, u, dist, usedEdges, usedVertex, routesPerDistance);
    }
}

int Calculate(vector<vector<Edge*>> & gr, vector<bool> & usedEdges, int v, int & n, int & k)
{
    Edge * edge = NULL;
    vector<bool> usedVertex(n, false);
    MaxEdgeSearch(gr, v, usedEdges, usedVertex, edge);

    if (edge == NULL)
    {
        //graph is empty
        return 0;
    }

    int from = edge -> from;
    int to = edge -> to;
    int weight = edge -> weight;
    int edgeId = edge -> id;

    usedEdges[edgeId] = true;
    map<int, int> dist;
    dist[from] = 0;
    dist[to] = 0;

    map<int, int> leftRoutesByDistance;
    map<int, int> rightRoutesByDistance;

    leftRoutesByDistance[0] = rightRoutesByDistance[0] = 1;

    CalculateDistance(gr, from, dist, usedEdges, usedVertex, leftRoutesByDistance);
    CalculateDistance(gr, to, dist, usedEdges, usedVertex, rightRoutesByDistance);

    int maxEdgesCount = weight - 1 - k;
    int ans = 0;

    for (int i = 0; i <= maxEdgesCount; i++)
    {
        for (int j = 0; j <= maxEdgesCount - i; j++)
            ans += 2 * leftRoutesByDistance[i] * rightRoutesByDistance[j];
    }

    ans += Calculate(gr, usedEdges, from, n, k);
    ans += Calculate(gr, usedEdges, to, n, k);

    return ans;
}

int main()
{
    int n, k, a, b, c;
    cin >> n >> k;
    int ans = 0;

    vector<bool> usedEdges(n, false);
    vector<vector<Edge*>> gr(n, vector<Edge*>());

    for (int i = 1; i < n ; i++)
    {
        cin >> a >> b >> c;
        Edge * edge = new Edge(a - 1, b - 1, c, i);
        gr[a - 1].push_back(edge);
        gr[b - 1].push_back(edge);
    }

    ans = Calculate(gr, usedEdges, 0, n, k);
    cout<<ans<<endl;
    return 0;
}