Open F4NT0 opened 2 months ago
using System;
using System.Collections.Generic;
public class Solution {
public int[] SumOfDistancesInTree(int n, int[][] edges) {
int[] ans = new int[n];
int[] count = new int[n];
HashSet<int>[] tree = new HashSet<int>[n];
for (int i = 0; i < n; ++i) {
tree[i] = new HashSet<int>();
count[i] = 1;
}
foreach (int[] edge in edges) {
int u = edge[0];
int v = edge[1];
tree[u].Add(v);
tree[v].Add(u);
}
Postorder(tree, 0, -1, count, ans);
Preorder(tree, 0, -1, count, ans);
return ans;
}
private void Postorder(HashSet<int>[] tree, int node, int parent, int[] count, int[] ans) {
foreach (int child in tree[node]) {
if (child == parent)
continue;
Postorder(tree, child, node, count, ans);
count[node] += count[child];
ans[node] += ans[child] + count[child];
}
}
private void Preorder(HashSet<int>[] tree, int node, int parent, int[] count, int[] ans) {
foreach (int child in tree[node]) {
if (child == parent)
continue;
ans[child] = ans[node] - count[child] + (tree.Length - count[child]);
Preorder(tree, child, node, count, ans);
}
}
}
There is an undirected connected tree with
n
nodes labeled from0
ton - 1
andn - 1
edges.You are given the integer
n
and the arrayedges
whereedges[i] = [ai, bi]
indicates that there is an edge between nodesai
andbi
in the tree.Return an array
answer
of lengthn
whereanswer[i]
is the sum of the distances between theith
node in the tree and all other nodes.Example 1
Example 2
Example 3
Constraints: