思路：
题目的主要信息：
- 一棵树每边长度为1，
节点到
节点的距离为
- 某个节点
- 现求树每个节点的权值
方法一：两次dfs
具体做法：
我们可以用两次dfs解决这个问题。
第一次dfs遍历这棵树，找到每个节点有多少个子节点，第二次dfs遍历每个节点，根据第一次找到的子节点数推算出到其他任何节点的距离。
public:
vector<int> G[100001];
vector<int> s; //记录每个子树的结点数
vector<long> res;
int dfs1(int u, int p, int d){ //u为当前节点，p为递归过来的前一个结点
int cnt = 1;
for(int i = 0; i < G[u].size(); i++)
if(G[u][i] != p)
cnt += dfs1(G[u][i], u, d + 1);
res[0] += d;
s[u] = cnt;
return cnt;
}
void dfs2(int u, int p, int n){//u为当前节点，p为前一个结点
for(int i = 0; i < G[u].size(); i++){
if(G[u][i] != p){
res[G[u][i]] = res[u] + n - 2 * s[G[u][i]];
dfs2(G[u][i], u, n);
}
}
}
vector<long> solve(int n, vector<Point>& edge) {
s.resize(n);
res.resize(n);
for(int i = 0; i < edge.size(); i++){ //构建图
G[edge[i].x - 1].push_back(edge[i].y - 1);
G[edge[i].y - 1].push_back(edge[i].x - 1);
}
dfs1(0, -1, 0); //深度优先每一个节点，计算每个子树有多少节点
dfs2(0, -1, n); //根据每个子树节点数，计算到每个节点的距离和
return res;
}
}; 复杂度分析：
- 时间复杂度：
，两次dfs递归，各自遍历每一个节点
- 空间复杂度：
方法二：bfs
具体做法：
因为树的bfs是层次遍历，对于每一层，祖先节点到其的距离都是相同的，利用这个性质，我们可以对于每一个节点进行遍历，然后以该节点作为bfs的起点开始计算总的距离。到达每一层的时，队列中的元素个数就是这一层的节点数，只需要加上该层的层号即是距离。
class Solution {
public:
int bfs(vector<vector<int>>& g, int n, int start) {
deque<int> q{{start}};
vector<bool> vis(n + 1, false);
vis[start] = true;
long res = 0;
int layers = 0; //层数
while(!q.empty()) {
int s = q.size(); //当前层节点数
while(s--){ //一层内距离相同
int cur = q.front();
q.pop_front();
res += layers;
for(int i = 0; i < g[cur].size(); i++){
if(vis[g[cur][i]]) //没有访问过的
continue;
vis[g[cur][i]] = true;
q.push_back(g[cur][i]);
}
}
layers++; //层数增加
}
return res;
}
vector<long> solve(int n, vector<Point>& edge) {
vector<long> res(n);
vector<vector<int> > G(n + 1);
for(int i = 0; i < edge.size(); i++){ //构建图
G[edge[i].x].push_back(edge[i].y);
G[edge[i].y].push_back(edge[i].x);
}
for (int i = 1; i <= n; i++)//遍历每个节点，bfs求距离
res[i - 1] = bfs(G, n, i);
return res;
}
};复杂度分析：
- 时间复杂度：
，对于每个节点，都有一次bfs，每次复杂度为
- 空间复杂度：
京公网安备 11010502036488号