【leetcode】834. Sum of Distances in Tree(图算法)
2024-09-08 05:29:27
There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given the integer n and the array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. Return an array answer of length n where answer[i] is the sum of the distances between the ith node in the tree and all other nodes.
Example 1:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]] Output: [8,12,6,10,10,10] Explanation: The tree is shown above. We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) equals 1 + 1 + 2 + 2 + 2 = 8. Hence, answer[0] = 8, and so on.
class Solution {
public:
vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
//好久没做和图论相关的题目了 图论的题目 dfs bfs?
//链接图链表
vector<int> res(n),count(n);
vector<vector<int>> tree(n);
for(auto &edge:edges)
{
tree[edge[0]].push_back(edge[1]);
tree[edge[1]].push_back(edge[0]); }
helper(tree,0,-1,count,res);
helper2(tree,0,-1,count,res);
return res; } void helper(vector<vector<int>> &tree,int cur,int pre,vector<int>&count,vector<int>& res)
{
for(int i:tree[cur])
{
if(i==pre) continue;
helper(tree,i,cur,count,res);
count[cur]+=count[i];//这个统计更新的逻辑 还是不懂。。
res[cur]+=res[i]+count[i];
}
++count[cur];
}
void helper2(vector<vector<int>> &tree,int cur,int pre,vector<int>&count,vector<int>& res)
{
for(int i:tree[cur])
{
if(i==pre) continue;
res[i]=res[cur]-count[i]+count.size()-count[i];
helper2(tree, i, cur, count, res);
}
}
};
最新文章
- AspNetPager 多条件分页查询
- js简单操作Cookie
- 位图图像处理控件ImageCapture Suite更新至v9.1
- Java设计模式-访问者模式(Visitor)
- VC 中 UpdateData() 函数的使用
- Markdown语法和MWeb使用说明
- Velocity源码分析
- maven install 报错Could not calculate build plan: Plugin org.apache.maven.plugins:maven-resources-plugin
- tabBar自定义
- javaCV图像处理之Frame、Mat和IplImage三者相互转换(使用openCV进行Mat和IplImage转换)
- iOS 开发之 Xcode installation failed invalid argument!
- 记一次jar包冲突
- mysql 远程连接配置
- 写一个python的服务监控程序
- 分析“HTTP500内部服务器错误”解决方法
- leetcode101
- LwIP协议栈接口
- shell脚本学习之参数传递
- nginx check_http_send type=http 查检测不到后端TOM的存活
- java队列queue的我觉得很好的使用方式