sum-of-distances-in-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is an undirected connected tree with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code> and <code>n - 1</code> edges.

You are given the integer <code>n</code> and the array <code>edges</code> where <code>edges[i] = [ai, bi]</code> indicates that there is an edge between nodes <code>ai</code> and <code>bi</code> in the tree.

Return an array <code>answer</code> of length <code>n</code> where <code>answer[i]</code> is the sum of the distances between the <code>ith</code> node in the tree and all other nodes.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist1.jpg" style="width: 304px; height: 224px;" />
<pre>
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist2.jpg" style="width: 64px; height: 65px;" />
<pre>
Input: n = 1, edges = []
Output: [0]
</pre>

Example 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist3.jpg" style="width: 144px; height: 145px;" />
<pre>
Input: n = 2, edges = [[1,0]]
Output: [1,1]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 3 * 104</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi &lt; n</code></li>
	<li><code>ai != bi</code></li>
	<li>The given input represents a valid tree.</li>
</ul>

sumOfDistancesInTree

Sum of Distances in Tree

Distribute Coins in Binary Tree

distribute-coins-in-binary-tree

在二叉树中分配硬币

Count Nodes With the Highest Score

count-nodes-with-the-highest-score

统计最高分的节点数目

Collect Coins in a Tree

collect-coins-in-a-tree

收集树中金币

Maximum Score After Applying Operations on a Tree

maximum-score-after-applying-operations-on-a-tree

在树上执行操作以后得到的最大分数

Count Pairs of Connectable Servers in a Weighted Tree Network

count-pairs-of-connectable-servers-in-a-weighted-tree-network

在带权树网络中统计可连接服务器对数目

Time Taken to Mark All Nodes

time-taken-to-mark-all-nodes

标记所有节点需要的时间

Tree

Depth-First Search

Graph

Dynamic Programming

给定一个无向、连通的树。树中有 <code>n</code> 个标记为 <code>0...n-1</code> 的节点以及 <code>n-1</code>&nbsp;条边&nbsp;。

给定整数 <code>n</code> 和数组&nbsp;<code>edges</code>&nbsp;，&nbsp;<code>edges[i] = [ai, bi]</code>表示树中的节点&nbsp;<code>ai</code>&nbsp;和&nbsp;<code>bi</code>&nbsp;之间有一条边。

返回长度为 <code>n</code> 的数组&nbsp;<code>answer</code>&nbsp;，其中&nbsp;<code>answer[i]</code>&nbsp;是树中第 <code>i</code> 个节点与所有其他节点之间的距离之和。

&nbsp;

示例 1:

<img src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist1.jpg" />

<pre>
输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。
</pre>

示例 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist2.jpg" />
<pre>
输入: n = 1, edges = []
输出: [0]
</pre>

示例 3:
<img alt="" src="https://assets.leetcode.com/uploads/2021/07/23/lc-sumdist3.jpg" />
<pre>
输入: n = 2, edges = [[1,0]]
输出: [1,1]
</pre>

&nbsp;

提示:

<ul>
	<li><code>1 &lt;= n &lt;= 3 * 104</code></li>
	<li><code>edges.length == n - 1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>0 &lt;= ai, bi&nbsp;&lt; n</code></li>
	<li><code>ai&nbsp;!= bi</code></li>
	<li>给定的输入保证为有效的树</li>
</ul>