文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個無向、連通的樹。樹中有 N 個標(biāo)記為 0...N-1 的節(jié)點(diǎn)以及 N-1 條邊 。

第 i 條邊連接節(jié)點(diǎn) edges[i][0] 和 edges[i][1] 。

返回一個表示節(jié)點(diǎn) i 與其他所有節(jié)點(diǎn)距離之和的列表 ans。

示例 1: 輸入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] 輸出: [8,12,6,10,10,10] 解釋: 如下為給定的樹的示意圖：0/ \ 1 2/|\3 4 5我們可以計算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此類推。 說明: 1 <= N <= 10000

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sum-of-distances-in-tree
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 抄的官方答案

class Solution {vector<int> ans, son, dp;vector<vector<int>> g; public:vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {ans.resize(N);son.resize(N);dp.resize(N);g.resize(N);for(auto& e : edges){g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}dfs1(0, -1);//dp 初始化dfs2(0, -1);//dp 遞推return ans;}void dfs1(int u, int f){ //求子樹包含的節(jié)點(diǎn)數(shù)量// 第一次dfs 得到的每個節(jié)點(diǎn)子樹節(jié)點(diǎn)到該節(jié)點(diǎn)的距離和son[u] = 1;dp[u] = 0;for(auto v : g[u]){if(v == f)continue;dfs1(v, u);dp[u] += dp[v]+son[v];//子節(jié)點(diǎn)的距離和 + 邊被占用次數(shù)son[u] += son[v];}}void dfs2(int u, int f){ans[u] = dp[u];for(auto v : g[u]){if(v == f)continue;int dpu = dp[u], dpv = dp[v];//記錄狀態(tài)int sonu = son[u], sonv = son[v];dp[u] -= dp[v]+son[v];//跟換根節(jié)點(diǎn)為 v ，u 變成子節(jié)點(diǎn)son[u] -= son[v];dp[v] += dp[u]+son[u];// v 加上 u 的數(shù)據(jù)son[v] += son[u];dfs2(v, u);dp[u] = dpu, dp[v] = dpv;//回溯狀態(tài)son[u] = sonu, son[v] = sonv;}} };

148 ms 26.4 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的LeetCode 834. 树中距离之和（树上DP）*的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。