Задача: 1519. Number of Nodes in the Sub-Tree With the Same Label
Сложность: medium

Вам дано дерево (т.е. связный неориентированный граф без циклов), состоящее из n узлов, пронумерованных от 0 до n - 1, и ровно n - 1 ребра. Корнем дерева является узел 0, и каждый узел дерева имеет метку, которая является строчной буквой, указанной в строке labels (т.е. узел с номером i имеет метку labels[i]).

Массив edges дан в форме edges[i] = [ai, bi], что означает, что существует ребро между узлами ai и bi в дереве.

Верните массив размера n, где ans[i] — это количество узлов в поддереве узла i, которые имеют ту же метку, что и узел i.

Поддерево дерева T — это дерево, состоящее из узла в T и всех его дочерних узлов.

Пример:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).

👨‍💻 Алгоритм:

1⃣Создайте список смежности, где adj[X] содержит всех соседей узла X.

2⃣Инициализируйте массив ans, хранящий ответ для каждого узла, и заполните его нулями.

3⃣Начните обход в глубину (DFS).

😎 Решение

var dfs = function(node, parent, adj, labels, ans) {
    const nodeCounts = new Array(26).fill(0);
    nodeCounts[labels.charCodeAt(node) - 97] = 1;

    if (!adj.has(node)) return nodeCounts;

    for (const child of adj.get(node)) {
        if (child === parent) continue;
        const childCounts = dfs(child, node, adj, labels, ans);
        for (let i = 0; i < 26; i++) {
            nodeCounts[i] += childCounts[i];
        }
    }

    ans[node] = nodeCounts[labels.charCodeAt(node) - 97];
    return nodeCounts;
};

var countSubTrees = function(n, edges, labels) {
    const adj = new Map();
    for (const [a, b] of edges) {
        if (!adj.has(a)) adj.set(a, []);
        if (!adj.has(b)) adj.set(b, []);
        adj.get(a).push(b);
        adj.get(b).push(a);
    }

    const ans = new Array(n).fill(0);
    dfs(0, -1, adj, labels, ans);
    return ans;
};

Ставь 👍 и забирай 📚 Базу знаний