leetcode

commit bfba29bc0d58e93396e2c2e577ca15fb4b290af7
parent 548b278c47a844fa8d443ba36fcfecdc89a37bc7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Thu, 12 Jan 2023 20:18:54 +0100

Daily Problem

Diffstat:
A
Problems/1519.cpp
 | 
42
++++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 43 insertions(+), 0 deletions(-)
diff --git a/Problems/1519.cpp b/Problems/1519.cpp
@@ -0,0 +1,42 @@
+class Solution {
+public:
+  vector<int> countSubTrees(int n, vector<vector<int>> &edges, string labels) {
+    vector<vector<int>> adj(n, vector<int>());
+    vector<vector<int>> count(n, vector<int>(26, 0));
+    vector<int> res(n);
+
+    for (auto &e : edges) {
+      adj[e[0]].push_back(e[1]);
+      adj[e[1]].push_back(e[0]);
+    }
+
+    stack<pair<int, int>> st;
+    st.push({0, -1});
+    while (!st.empty()) {
+      if (st.top().first == -1) {
+        st.pop();
+
+        auto [crnt, par] = st.top();
+        st.pop();
+
+        for (int c : adj[crnt]) {
+          if (c == par) continue;
+          for (int i = 0; i < 26; i++) count[crnt][i] += count[c][i];
+        }
+
+        res[crnt] = ++count[crnt][labels[crnt] - 'a'];
+        continue;
+      }
+
+      auto [crnt, par] = st.top();
+      st.push({-1, -1});
+
+      for (int c : adj[crnt]) {
+        if (c == par) continue;
+        st.push({c, crnt});
+      }
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -261,6 +261,7 @@ for solving problems.
 |  1480  |    Easy    | [Running Sum of 1d Array](Problems/1480.cpp)                                                     |
 |  1489  |    Hard    | [Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree](Problems/1489.cpp)            |
 |  1514  |   Medium   | [Path with Maximum Probability](Problems/1514.cpp)                                               |
+|  1519  |   Medium   | [Number of Nodes in the Sub-Tree With the Same Label](Problems/1519.cpp)                         |
 |  1544  |    Easy    | [Make The String Great](Problems/1544.cpp)                                                       |
 |  1557  |   Medium   | [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp)                               |
 |  1584  |   Medium   | [Min Cost to Connect All Points](Problems/1584.cpp)                                              |