小团作为一名美团骑手,最喜欢的颜色就是黄和黑,因此对包含这两种颜色的事物都格外留意。 这天他发现有一棵树,树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点,在以其为根的子树中,所有与其颜色不同的节点的深度之和是多少 。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。-笔试面试资料

这是qklbishe.com第15022 篇笔试面试资料
提供答案分析,通过本文《小团作为一名美团骑手,最喜欢的颜色就是黄和黑,因此对包含这两种颜色的事物都格外留意。 这天他发现有一棵树,树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点,在以其为根的子树中,所有与其颜色不同的节点的深度之和是多少 。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

小团作为一名美团骑手,最喜欢的颜色就是黄和黑,因此对包含这两种颜色的事物都格外留意。

这天他发现有一棵树,树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点,在以其为根的子树中,所有与其颜色不同的节点的深度之和是多少。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。

小团作为一名美团骑手,最喜欢的颜色就是黄和黑,因此对包含这两种颜色的事物都格外留意。       这天他发现有一棵树,树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点,在以其为根的子树中,所有与其颜色不同的节点的深度之和是多少 。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。
小团作为一名美团骑手,最喜欢的颜色就是黄和黑,因此对包含这两种颜色的事物都格外留意。       这天他发现有一棵树,树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点,在以其为根的子树中,所有与其颜色不同的节点的深度之和是多少 。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。 区块链毕设学生474721145号
#include <iostream> #include <vector> #include <map> #include <queue> using namespace std; vector<long long> handle(vector<int>& colors, map<int, vector<int>>& edges) {     int n = colors.size() - 1;     vector<long long> ret(n);     vector<vector<int>> tree;     queue<int> q;     q.push(1);     //构建树并记录每一层的节点     while(!q.empty()) {         int sz = q.size();         vector<int> floor;         for(int i = 0; i< sz; i++) {             int node = q.front();             q.pop();             floor.push_back(node);             for(auto j : edges[node]) {                 q.push(j);             }         }         tree.push_back(floor);     }     vector<vector<int>> data(n+1, vector<int>(4));     int m = tree.size();     // 从最后一层开始遍历,更新每个节点包含的红黑节点数量及其深度之和     for(int i = m-1; i >= 0; i--) {         for(auto j : tree[i]) {             if(edges[j].empty()) {                 if(colors[j]) {                     data[j] = {0, 0, 1, 0};                 } else {                     data[j] = {1, 0, 0, 0};                 }             } else {                 for(auto k : edges[j]){                     data[j][0] += data[k][0];                     data[j][1] += data[k][0] + data[k][1];                     data[j][2] += data[k][2];                     data[j][3] += data[k][2] + data[k][3];                 }                 if(colors[j]) {                     data[j][2] += 1;                     ret[j-1] = data[j][1];                 } else {                     data[j][0] += 1;                     ret[j-1] = data[j][3];                 }             }         }     }     return ret; } int main() {     int n;     cin >> n;     vector<int> colors(n+1);     map<int, vector<int>> edges;     for(int i = 1; i <= n; i++) {         cin >> colors[i];     }     int node;     for(int i = 1; i <= n-1; i++) {         cin >> node;         edges[node].push_back(i+1);     }     for(auto i : handle(colors, edges)) {         cout << i << " ";     }     return 0; } 

今天 00:17:31 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小团作为一名美团骑手,最喜欢的颜色就是黄和黑,因此对包含这两种颜色的事物都格外留意。 这天他发现有一棵树,树上的每个节点都是黄的或者黑的。现在小团想知道对于这棵树中的每个节点,在以其为根的子树中,所有与其颜色不同的节点的深度之和是多少 。子树中节点的深度被定义为该节点与该子树根节点之间的最短路径的边数。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情