原题目：https://leetcode-cn.com/problems/sum-of-distances-in-tree/
思路：
采用树形动态规划的思想。对于每一个节点来说，所有节点到他的距离之和的状态转移方程为：
其中dp[v]代表以v为根的所有节点到他的距离，sz[v]表示已v为根的子树节点的数量。
当一次遍历完，得到了所有节点的dp时，我们不需要以另一个节点为根重新遍历，只需要对树结构进行变化（官方解答的视频），所以每一次做变化我们只需要变换dp[u],sz[u],dp[v],sz[u]就可以。很容易想到变换规则如下：
dp[u] = dp[u] - (dp[v] + sz[v])
sz[u] = sz[u] - sz[v] dp[v] = dp[v] + (dp[u] + sz[u])
sz[v] = sz[v] + sz[u]
代码：
class Solution { private: vector<int> ans,dp,sz; vector<vector<int>> g; void dfs(int u,int f){ for(int& i:g[u]){ if(i==f) continue; dfs(i,u); dp[u] += dp[i]+sz[i]; sz[u] += sz[i]; } } void dfs2(int u,int f){ ans[u] = dp[u]; //对树结构进行变化 for(int& i:g[u]){ if(i==f) continue; int si=sz[i],su=sz[u]; int di = dp[i], du = dp[u]; dp[u] -= (dp[i] + sz[i]); sz[u] -= sz[i]; dp[i] += (dp[u] + sz[u]); sz[i] += sz[u]; dfs2(i,u); sz[i]=si;sz[u]=su; dp[i]=di,dp[u]=du; } } public: vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) { ans.resize(N,0); dp.resize(N,0); sz.resize(N,1); g.resize(N,{}); // 构建原图 for(auto& i:edges){ g[i[0]].push_back(i[1]); g[i[1]].push_back(i[0]); } dfs(0,-1);//获取dp dfs2(0,-1);//使用计算得更新ans return ans; } };
