Count Tree Paths With Limited Maximum Edge Weight – Complete C# Tutorial

1. Introduction

In this article, we will understand how to solve the Count Tree Paths With Limited Max Edge Weight problem using C#.

This problem is based on three important concepts:

1. Tree – A connected graph without cycles.

2. Sorting – Processing edges based on their weights.

3. Disjoint Set Union (DSU) – Managing connected components efficiently.

The main challenge is to count all possible distinct paths between two different nodes where the maximum edge weight along the path does not exceed the given query value.

Instead of checking every possible path, we use DSU to calculate the answer efficiently.

2. Understanding the problem

We are given:

• n – Number of nodes.

• edges – Connections between nodes with weights.

• queries – Maximum allowed edge weights.

For every query x, we need to count the number of distinct paths where every edge in the path has a weight less than or equal to x.

Remember:

• A path from 1 to 2 is the same as a path from 2 to 1.

• A node cannot form a path with itself.

• A path must contain at least one edge.

Example 1

Input:

n = 3;

edges = new int[][]
{
    new int[] { 1, 2, 1 },
    new int[] { 2, 3, 4 }
};

queries = new int[] { 3 };

Tree representation:

Allowed edge

Not allowed edge

Query = 3.

Only the edge with weight 1 is allowed.

Valid paths:

- 1 → 2

The path 1 → 3 is not allowed because it contains an edge with weight 4.

Output:

[1]

3. Understand the important mathematical concept

This is the most important part of the problem.

Suppose we have two separate connected components:

Component A:          Component B:

1 ---- 2              4 ---- 5 ---- 6

Component A has 2 nodes.

Component B has 3 nodes.

Now, if we connect these components using a new edge:

1 ---- 2 ---- 4 ---- 5 ---- 6

How many new paths are created?

Every node in Component A can form a path with every node in Component B.

Total new paths:

\[ 2 \times 3 = 6 \]

Therefore, the formula is:

\[ \boxed{NewPaths = SizeA \times SizeB} \]

We use this formula whenever two different connected components are merged.

4. What is Disjoint Set Union (DSU)?

DSU stands for Disjoint Set Union. It is also known as Union-Find.

It is used to manage multiple independent groups of nodes.

DSU has two important operations:

1. Find()

Finds the root or representative of a node's component.

2. Union()

Combines two different components into one component.

Initially

Every node belongs to its own component.

1    2    3    4    5

Parent array:

parent = [1, 2, 3, 4, 5]

Component sizes:

size = [1, 1, 1, 1, 1]

After Union(1, 2)

1 ---- 2    3    4    5

Now nodes 1 and 2 belong to the same component.

After Union(2, 3)

1 ---- 2 ---- 3    4    5

Now the component contains three nodes.

Its size is 3.

This is how DSU maintains connected components.

5. Important DSU optimizations

We use two optimizations to make the algorithm efficient.

A. Path Compression

Consider this parent relationship:

1 → 2 → 3 → 4

When we call:

Find(1);

The root is node 4.

Path compression updates the parent relationships so that future Find operations become faster.

int Find(int x)
{
    if (parent[x] != x)
    {
        parent[x] = Find(parent[x]);
    }

    return parent[x];
}

Explanation:

• Check whether the current node is its own parent.

• If not, recursively find its root.

• Update its parent directly to the root.

• Return the root.

B. Union by Size

When merging two components, we attach the smaller component to the larger component.

if (size[rootA] < size[rootB])
{
    int temp = rootA;
    rootA = rootB;
    rootB = temp;
}

parent[rootB] = rootA;
size[rootA] += size[rootB];

Why?

Because attaching smaller trees under larger trees helps keep the DSU structure shallow.

6. Complete C# solution

Now let's combine everything into the requested class.

class Solution
{
    int[] parent;
    int[] size;

    // Find the root parent of a node
    int Find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = Find(parent[x]);
        }

        return parent[x];
    }

    // Merge two connected components
    void Union(int a, int b, ref int totalPaths)
    {
        int rootA = Find(a);
        int rootB = Find(b);

        // Already in the same component
        if (rootA == rootB)
        {
            return;
        }

        // Count new paths
        totalPaths += size[rootA] * size[rootB];

        // Union by Size
        if (size[rootA] < size[rootB])
        {
            int temp = rootA;
            rootA = rootB;
            rootB = temp;
        }

        parent[rootB] = rootA;

        size[rootA] += size[rootB];
    }

    public List<int> maximumWeight(
        int n, int[][] edges, int[] queries)
    {
        // Sort edges based on weight
        Array.Sort(edges,
            (a, b) => a[2].CompareTo(b[2]));

        // Sort query indexes
        int q = queries.Length;

        int[] indexes = new int[q];

        for (int i = 0; i < q; i++)
        {
            indexes[i] = i;
        }

        Array.Sort(indexes,
            (a, b) => queries[a].CompareTo(queries[b]));

        // Initialize DSU
        parent = new int[n + 1];
        size = new int[n + 1];

        for (int i = 1; i <= n; i++)
        {
            parent[i] = i;
            size[i] = 1;
        }

        int[] answer = new int[q];

        int edgeIndex = 0;
        int totalPaths = 0;

        // Process queries in sorted order
        foreach (int queryIndex in indexes)
        {
            int limit = queries[queryIndex];

            // Process all eligible edges
            while (edgeIndex < edges.Length &&
                   edges[edgeIndex][2] <= limit)
            {
                int u = edges[edgeIndex][0];
                int v = edges[edgeIndex][1];

                Union(u, v, ref totalPaths);

                edgeIndex++;
            }

            // Save answer in original query order
            answer[queryIndex] = totalPaths;
        }

        return new List<int>(answer);
    }
}