aboutsummaryrefslogtreecommitdiffstats
path: root/834
diff options
context:
space:
mode:
authorterminaldweller <thabogre@gmail.com>2022-12-22 05:50:55 +0000
committerterminaldweller <thabogre@gmail.com>2022-12-22 05:50:55 +0000
commitee04b1c58c5480a6122a60bdb58b03c1e31c55fe (patch)
treeff66c30b715ec239ddb0ab7b633ed72baef6c820 /834
parent886 (diff)
downloadleetcode-ee04b1c58c5480a6122a60bdb58b03c1e31c55fe.tar.gz
leetcode-ee04b1c58c5480a6122a60bdb58b03c1e31c55fe.zip
834
Diffstat (limited to '834')
-rw-r--r--834/go.mod3
-rw-r--r--834/main.go51
2 files changed, 54 insertions, 0 deletions
diff --git a/834/go.mod b/834/go.mod
new file mode 100644
index 0000000..2a95dd6
--- /dev/null
+++ b/834/go.mod
@@ -0,0 +1,3 @@
+module 834
+
+go 1.19
diff --git a/834/main.go b/834/main.go
new file mode 100644
index 0000000..c2392f0
--- /dev/null
+++ b/834/main.go
@@ -0,0 +1,51 @@
+package main
+
+import "fmt"
+
+func dfs(node int, parent int, adjList map[int][]int, count []int, result []int) {
+ for _, child := range adjList[node] {
+ if child == parent {
+ continue
+ }
+
+ dfs(child, node, adjList, count, result)
+ count[node] += count[child]
+ result[node] += result[child] + count[child]
+ }
+}
+
+func dfs2(node int, parent int, adjList map[int][]int, count []int, result []int) {
+ for _, child := range adjList[node] {
+ if child == parent {
+ continue
+ }
+
+ result[child] = result[node] - count[child] + len(count) - count[child]
+ dfs2(child, node, adjList, count, result)
+ }
+}
+
+func sumOfDistancesInTree(n int, edges [][]int) []int {
+ adjList := make(map[int][]int)
+
+ for _, edge := range edges {
+ adjList[edge[0]] = append(adjList[edge[0]], edge[1])
+ adjList[edge[1]] = append(adjList[edge[1]], edge[0])
+ }
+
+ count := make([]int, n)
+ for i := 0; i < len(count); i++ {
+ count[i] = 1
+ }
+
+ result := make([]int, n)
+
+ dfs(0, -1, adjList, count, result)
+ dfs2(0, -1, adjList, count, result)
+
+ return result
+}
+
+func main() {
+ fmt.Println("vim-go")
+}