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

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

✓ Dp 2d

⏱️ Time: N/A Space: N/A

Memoization

⏱️ Time: N/A Space: N/A

Brute Force - Check All Triplets

⏱️ Time: O(n³) Space: O(n)

For every possible central server c, check all pairs of other servers (a,b) where a < b, calculate distances using BFS/DFS, and verify if both distances are divisible by signalSpeed and paths don't share edges.

DFS with Subtree Counting

⏱️ Time: O(n²) Space: O(n)

For each potential central server, perform DFS to explore all subtrees. Count servers at distances divisible by signalSpeed in each subtree, then calculate pairs between different subtrees.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

struct Edge {
    int to, weight;
    struct Edge* next;
};

struct Edge* adj[1001];
int visited[1001];
int distances[1001];
int subtree_id[1001];

void addEdge(int from, int to, int weight) {
    struct Edge* edge = (struct Edge*)malloc(sizeof(struct Edge));
    edge->to = to;
    edge->weight = weight;
    edge->next = adj[from];
    adj[from] = edge;
}

void dfs(int node, int parent, int dist, int hub, int subtree) {
    visited[node] = 1;
    distances[node] = dist;
    subtree_id[node] = subtree;
    
    struct Edge* edge = adj[node];
    while (edge != NULL) {
        if (edge->to != parent && edge->to != hub) {
            dfs(edge->to, node, dist + edge->weight, hub, subtree);
        }
        edge = edge->next;
    }
}

int countPairs(int n, int hub, int signalSpeed) {
    // Reset arrays
    for (int i = 0; i < n; i++) {
        visited[i] = 0;
        distances[i] = -1;
        subtree_id[i] = -1;
    }
    
    // For each neighbor of hub, start DFS to build subtrees
    int subtree_count = 0;
    struct Edge* edge = adj[hub];
    while (edge != NULL) {
        if (!visited[edge->to]) {
            dfs(edge->to, hub, edge->weight, hub, subtree_count);
            subtree_count++;
        }
        edge = edge->next;
    }
    
    // Collect valid nodes (distance divisible by signalSpeed) grouped by subtree
    int valid_in_subtree[1001] = {0};
    int valid_nodes[1001];
    int valid_count = 0;
    
    for (int i = 0; i < n; i++) {
        if (i != hub && distances[i] != -1 && distances[i] % signalSpeed == 0) {
            valid_nodes[valid_count] = i;
            valid_in_subtree[subtree_id[i]]++;
            valid_count++;
        }
    }
    
    // Count pairs from different subtrees
    int pairs = 0;
    for (int i = 0; i < valid_count; i++) {
        for (int j = i + 1; j < valid_count; j++) {
            int a = valid_nodes[i];
            int b = valid_nodes[j];
            if (a > b) { int temp = a; a = b; b = temp; }
            
            // Check if they're in different subtrees
            if (subtree_id[a] != subtree_id[b]) {
                pairs++;
            }
        }
    }
    
    return pairs;
}

void parseEdges(char* input, int edges[][3], int* edge_count) {
    int len = strlen(input);
    int i = 0;
    *edge_count = 0;
    
    while (i < len) {
        if (input[i] == '[' && i > 0) {
            i++;
            // Parse three numbers
            int nums[3];
            int num_idx = 0;
            
            while (i < len && input[i] != ']') {
                if (input[i] >= '0' && input[i] <= '9') {
                    int num = 0;
                    while (i < len && input[i] >= '0' && input[i] <= '9') {
                        num = num * 10 + (input[i] - '0');
                        i++;
                    }
                    nums[num_idx++] = num;
                } else {
                    i++;
                }
            }
            
            if (num_idx == 3) {
                edges[*edge_count][0] = nums[0];
                edges[*edge_count][1] = nums[1];
                edges[*edge_count][2] = nums[2];
                (*edge_count)++;
            }
        }
        i++;
    }
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    int edges[1000][3];
    int edge_count;
    parseEdges(input, edges, &edge_count);
    
    int signalSpeed;
    scanf("%d", &signalSpeed);
    
    // Find number of nodes
    int n = 0;
    for (int i = 0; i < edge_count; i++) {
        if (edges[i][0] > n) n = edges[i][0];
        if (edges[i][1] > n) n = edges[i][1];
    }
    n++;
    
    // Initialize adjacency list
    for (int i = 0; i < n; i++) {
        adj[i] = NULL;
    }
    
    // Build adjacency list
    for (int i = 0; i < edge_count; i++) {
        addEdge(edges[i][0], edges[i][1], edges[i][2]);
        addEdge(edges[i][1], edges[i][0], edges[i][2]);
    }
    
    // Calculate result for each hub
    printf("[");
    for (int hub = 0; hub < n; hub++) {
        int pairs = countPairs(n, hub, signalSpeed);
        printf("%d", pairs);
        if (hub < n - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

⚡ 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