Count Pairs of Connectable Servers in a Weighted Tree Network

Count Pairs of Connectable Servers in a Weighted Tree Network - Problem

You are given an unrooted weighted tree with n vertices representing servers numbered from 0 to n - 1, an array edges where edges[i] = [a_i, b_i, weight_i] represents a bidirectional edge between vertices a_i and b_i of weight weight_i.

You are also given an integer signalSpeed.

Two servers a and b are connectable through a server c if:

a < b
a != c and b != c
The distance from c to a is divisible by signalSpeed
The distance from c to b is divisible by signalSpeed
The path from c to a and the path from c to b do not share any edges

Return an integer array count of length n where count[i] is the number of server pairs that are connectable through the server i.

Input & Output

Example 1 — Basic Tree Network

$ Input: edges = [[0,1,1],[1,2,5],[2,3,13],[1,4,9],[4,5,2]], signalSpeed = 1

› Output: [0,4,0,0,0,0]

💡 Note: With signalSpeed=1, all distances are valid. Server 1 can connect 4 pairs through its central position in the tree structure.

Example 2 — Specific Signal Speed

$ Input: edges = [[0,6,3],[6,4,2],[6,3,3],[4,5,2],[4,1,4],[4,2,1]], signalSpeed = 3

› Output: [0,0,0,0,0,0,2]

💡 Note: Only server 6 can act as a hub. Distances must be divisible by 3, creating 2 valid pairs through server 6.

Example 3 — Linear Chain

$ Input: edges = [[0,1,2],[1,2,4]], signalSpeed = 2

› Output: [0,1,0]

💡 Note: In a 3-node linear chain, only the middle server (1) can connect the endpoints since both distances are divisible by 2.

Constraints

1 ≤ n ≤ 1000
edges.length == n - 1
1 ≤ a_i, b_i ≤ n - 1
a_i != b_i
1 ≤ weight_i ≤ 10⁶
1 ≤ signalSpeed ≤ 10⁶
The input represents a valid tree

Visualization

Tap to expand

Understanding the Visualization

Input

Tree network with weighted edges and signalSpeed requirement

Process

For each server as hub, count valid distance pairs to other servers

Output

Array showing connectable pairs count for each server as hub

Key Takeaway

🎯 Key Insight: In trees, paths from a central node to different subtrees never overlap, making pair counting efficient through DFS subtree exploration

Asked in

f Meta 12 G Google 8 a Amazon 6

The key insight is that in a tree, paths from any central node to different subtrees never share edges. The optimal approach uses DFS subtree counting to efficiently calculate valid pairs. For each potential central server, we count servers at valid distances in each subtree, then multiply counts between different subtrees. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Triplets	O(n³)	O(n)	Check every possible combination of three servers to see if two are connectable through the third
DFS with Subtree Counting	O(n²)	O(n)	Use DFS to explore each subtree from a central server and count valid distance pairs efficiently

Brute Force - Check All Triplets — Algorithm Steps

Step 1: Build adjacency list representation of the tree
Step 2: For each server c, try all pairs (a,b) where a < b and a,b != c
Step 3: Calculate distance from c to a and c to b using BFS
Step 4: Check if both distances are divisible by signalSpeed
Step 5: Verify paths don't share edges (automatically true in trees if different destinations)

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Center

Choose server c as potential hub

Check Pairs

Test all pairs (a,b) where a < b and both != c

Calculate

Find distances c→a and c→b, check divisibility

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000
#define MAX_QUEUE 10000

typedef struct {
    int node;
    int weight;
} Edge;

typedef struct {
    int node;
    int dist;
} QueueItem;

Edge graph[MAX_N][MAX_N];
int graphSize[MAX_N];

int getDistance(int n, int start, int end) {
    if (start == end) return 0;
    
    QueueItem queue[MAX_QUEUE];
    int visited[MAX_N] = {0};
    int front = 0, rear = 0;
    
    queue[rear++] = (QueueItem){start, 0};
    visited[start] = 1;
    
    while (front < rear) {
        QueueItem curr = queue[front++];
        
        for (int i = 0; i < graphSize[curr.node]; i++) {
            Edge neighbor = graph[curr.node][i];
            if (neighbor.node == end) {
                return curr.dist + neighbor.weight;
            }
            if (!visited[neighbor.node]) {
                visited[neighbor.node] = 1;
                queue[rear++] = (QueueItem){neighbor.node, curr.dist + neighbor.weight};
            }
        }
    }
    
    return -1;
}

int* solution(int** edges, int edgesSize, int* edgesColSize, int signalSpeed, int* returnSize) {
    if (edgesSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int n = edgesSize + 1;
    memset(graphSize, 0, sizeof(graphSize));
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int a = edges[i][0], b = edges[i][1], weight = edges[i][2];
        graph[a][graphSize[a]++] = (Edge){b, weight};
        graph[b][graphSize[b]++] = (Edge){a, weight};
    }
    
    int* result = (int*)calloc(n, sizeof(int));
    *returnSize = n;
    
    // For each server as center
    for (int c = 0; c < n; c++) {
        int count = 0;
        // Check all pairs (a, b) where a < b
        for (int a = 0; a < n; a++) {
            if (a == c) continue;
            for (int b = a + 1; b < n; b++) {
                if (b == c) continue;
                
                int distCA = getDistance(n, c, a);
                int distCB = getDistance(n, c, b);
                
                if (distCA % signalSpeed == 0 && distCB % signalSpeed == 0) {
                    count++;
                }
            }
        }
        
        result[c] = count;
    }
    
    return result;
}

int main() {
    // This is a simplified version for the problem
    // In practice, parsing 2D arrays in C from stdin is complex
    printf("[0,0,0]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n servers as center, check O(n²) pairs, each requiring O(n) distance calculation

⚠ Quadratic Growth

Space Complexity

O(n)

Adjacency list storage and BFS queue space

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Triplets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler