C ++中树的距离总和
假设我们有一棵无向的，连接的树，其中有N个节点。这些标记为0...N-1，给出了N-1边。第i条边将节点edge[i][0]和edge[i][1]连接在一起。我们必须找到一个列表，其中ans[i]是节点i与所有其他节点之间的距离之和。
因此，如果输入像N=6并且edges=[[(0,1)，(0,2)，(2,3)，(2,4)，(2,5)]，那么输出将为[8,12,6,10,10,10]
为了解决这个问题，我们将遵循以下步骤-
定义一个函数dfs1()，它将使用node，parent，
子：=graph[node，i]
如果孩子不等于父母，那么-
dfs1（子节点）
cnt[node]：=cnt[node]+cnt[child]
ans[node]：=ans[node]+cnt[child]+ans[child]
对于初始化i：=0，当i<graph[node]的大小时，更新（将i增加1），执行-
定义一个函数dfs2()，它将使用node，parent，
子：=graph[node，i]
如果孩子不等于父母，那么-
ans[child]：=ans[node]-cnt[child]+N-cnt[child]
dfs2（子节点
对于初始化i：=0，当i<graph[node]的大小时，更新（将i增加1），执行-
定义一个数组ans
定义一个数组cnt
定义具有10005行的数组图
从主要方法中，执行以下操作-
N个：=N
ans：=定义大小为N的数组
cnt：=定义一个大小为N的数组，并用1填充
n：=边的大小
对于初始化i：=0，当i<n时，更新（将i增加1），执行-
u：=edges[i，0]
v：=edges[i，1]
在图形的末尾插入v[u]
在图形[v]的末尾插入u
dfs1(0,-1)
dfs2(0,-1)
返回ans
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0;
i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
void dfs1(int node, int parent) {
for (int i = 0; i < graph[node].size(); i++) {
int child = graph[node][i];
if (child != parent) {
dfs1(child, node);
cnt[node] += cnt[child];
ans[node] += cnt[child] + ans[child];
}
}
}
void dfs2(int node, int parent) {
for (int i = 0; i < graph[node].size(); i++) {
int child = graph[node][i];
if (child != parent) {
ans[child] = ans[node] - cnt[child] + N - cnt[child];
dfs2(child, node);
}
}
}
vector<int> ans;
vector<int> cnt;
vector<int> graph[10005];
int N;
vector<int> sumOfDistancesInTree(int N, vector<vector<int> >& edges) {
this->N = N;
ans = vector<int>(N);
cnt = vector<int>(N, 1);
int n = edges.size();
for (int i = 0; i < n; i++) {
int u = edges[i][0];
int v = edges[i][1];
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs1(0, -1);
dfs2(0, -1);
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1},{0,2},{2,3},{2,4},{2,5}}; print_vector(ob.sumOfDistancesInTree(6, v));
}输入值
{{0,1},{0,2},{2,3},{2,4},{2,5}}输出结果
[8, 12, 6, 10, 10, 10, ]