C++/reroot DP動態規劃解Leetcode難題834 Sum of Distances in Tree

C++/reroot DP動態規劃解Leetcode難題834  Sum of Distances in Tree

關鍵字：reroot DP。 你會發現很多關於它的討論。

對於作為根的每個節點，進行 DFS，將獲得 O(n^2) 的解決方案，但可能 TLE。

使用一次遞迴 DFS 求 root=0 的樹中的距離和，計算每個節點 i 作為根的子樹中的節點數。

------

Keywords: reroot DP. You'll find a lot of discussion about it.

Doing DFS for each node that is a root, you will get a solution of O(n^2), but possible TLE.

Use a recursive DFS to find the sum of distances in the tree with root=0 and count the number of nodes in the subtree rooted at each node i.

[codes on Leetcode]https://leetcode.com/problems/sum-of-distances-in-tree/solutions/5081728/reroot-dp-dfs-165ms-beats-97-28/

[Dynamic programming playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5K_XYUesV9oc6M9ONXII61T

[Leetcode Playlist]https://www.youtube.com/watch?v=B1GQlUN08lk&list=PLYRlUBnWnd5IdDHk2BjqXwesydU17z_xk

[Fibonacci sequence playlist]https://www.youtube.com/watch?v=30yq3fmE6E8&list=PLYRlUBnWnd5Jb9PI7P1V2GEgOu1n3hki-