這道題我自己的想法只有對每個點都用一遍Dijkstra然后再求和，顯然會超時，所以我都沒有嘗試。

研究了一下題解，發現題解很巧妙，自己對樹的處理還是太稚嫩，之前樹鏈剖分學的都忘光了。

對于固定根節點的，我們應該使用樹狀dp：
$$dp[u]=\sum _{v\in son(u)}dp[v]+sz[v]$$
其中，$dp[u]$表示以u為根節點的子樹中根節點u到其兒子節點的所有距離之和，之所以加上$sz[v]$是因為長度為1，如果長度不固定的話只需要乘上長度就可以了。

通過上面的dp我們可以算出以一個節點為根節點的答案，但是其他節點呢？樸素的想法是對其他節點每個也進行相同的操作，這樣的時間復雜度是$O(n^2)$，好像還可以接受。

題解給出了更優秀的做法：假設我們已經求出了以節點u為根節點的樹的答案$dp[u]$，對于其直接孩子v，我們是有辦法直接求出以v為根節點的答案的。

最主要的性質是：如果更換了根節點，只會影響這兩個相鄰節點的dp值，對其他節點的dp值是不會有影響的。因此我們只需要更新這兩個節點即可。

首先我們應該從$dp[u]$中減去$dp[v]+sz[v]$，因為這個時候是以v為根節點的，然后更新$sz[u]$，然后再給$dp[v]$加上$dp[u]+sz[u]$，再更新$sz[v]$。這樣就得到了正確的答案。

代碼實現的話首先進行一次樹狀dp，然后再進行回溯。

發現題解中的代碼很精煉，仔細學習了一下自己實現了一個差不多的，幾乎沒有區別。學到了使用$emplace\_back$的復雜度好像更加優秀。

還是要多做hard題目，對自己的提升比較大。

class Solution {
public:vector<int> dp,sz,ans;vector< vector<int> > graph;void Init(int n, vector<vector<int> >&edges){dp.resize(n, 0);sz.resize(n, 0);ans.resize(n, 0);graph.resize(n, {});int u,v;for(auto& edge:edges){u = edge[0]; v = edge[1];graph[u].emplace_back(v);graph[v].emplace_back(u);}}void dfs(int u,int father){sz[u] = 1; dp[u] = 0;for(auto& v:graph[u]){if(v == father) continue;dfs(v, u);sz[u] += sz[v];dp[u] += dp[v] + sz[v];}}void dfs2(int u, int father){ans[u] = dp[u];int dpu, dpv, szu, szv;for(auto& v:graph[u]){if(v == father) continue;dpu = dp[u]; dpv = dp[v];szu = sz[u]; szv = sz[v];dp[u] -= dp[v] + sz[v];sz[u] -= sz[v];dp[v] += dp[u] + sz[u];sz[v] += sz[u];dfs2(v, u);dp[u] = dpu; dp[v] = dpv;sz[u] = szu; sz[v] = szv;}}vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {Init(N, edges);dfs(0, -1);dfs2(0, -1);return ans;}
};