做网站需要知道什么软件,建设银行苏州官网招聘网站,徐州html5响应式网站建设,软件开发制作的公司给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。返回一个表示节点 i 与其他所有节点距离之和的列表 ans。示例 1:输入: N 6, edges [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解…给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。返回一个表示节点 i 与其他所有节点距离之和的列表 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
代码
class Solution {int[] sz,dp,re;MapInteger,ListInteger map3new HashMap();public int[] sumOfDistancesInTree(int N, int[][] edges) {renew int[N];sznew int[N];dpnew int[N];for (int i0;iN;i)map3.put(i,new ArrayList());for(int[] edge:edges)//邻接表{map3.get(edge[0]).add(edge[1]);map3.get(edge[1]).add(edge[0]);}getSumOfDistancesInTree(0, -1);getSumOfDistancesInTree2(0, -1);return re;}public void getSumOfDistancesInTree(int cur, int father) {//从根节点向下统计距离dp[cur]0;sz[cur]1;for(int next:map3.get(cur)){if(nextfather) continue;getSumOfDistancesInTree(next,cur);dp[cur]dp[next]sz[next];sz[cur]sz[next];}}public void getSumOfDistancesInTree2(int cur, int father) {re[cur]dp[cur];for(int next:map3.get(cur)){if(nextfather) continue;int pndp[next],pcdp[cur],snsz[next],scsz[cur];dp[cur]-dp[next]sz[next];sz[cur]-sz[next];dp[next]dp[cur]sz[cur];sz[next]sz[cur];//将父子节点颠倒对应的值发生改变getSumOfDistancesInTree2(next,cur);dp[next]pn;dp[cur]pc;sz[cur]sc;sz[next]sn;//还原父子节点}}
}
