题意 在一颗有   个结点且 以 为根节点树上,起初每个结点的初始权值为 。 现在有 次操作,每次操作选择将以 为根节点的子树上的所有结点权值增加 。 求 次操作后从 到 每个结点的权值。 输入 第一个参数为 , 第二个参数为边 的集合,其中 表示结点 与结点 之间有一条边, 第三个参数为 , 第四个参数为 次询问的 的集合, 返回 从 到 每个结点的权值。-笔试面试资料

这是qklbishe.com第14405 篇笔试面试资料
提供答案分析,通过本文《题意 在一颗有   个结点且 以 为根节点树上,起初每个结点的初始权值为 。 现在有 次操作,每次操作选择将以 为根节点的子树上的所有结点权值增加 。 求 次操作后从 到 每个结点的权值。 输入 第一个参数为 , 第二个参数为边 的集合,其中 表示结点 与结点 之间有一条边, 第三个参数为 , 第四个参数为 次询问的 的集合, 返回 从 到 每个结点的权值。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

题意

在一颗有 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 个结点且题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 为根节点树上,起初每个结点的初始权值为 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。

现在有 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 次操作,每次操作选择将以 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 为根节点的子树上的所有结点权值增加 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。

题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 次操作后从 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 每个结点的权值。

输入

第一个参数为 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。

第二个参数为边 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 的集合,其中 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 表示结点 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 与结点 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 之间有一条边,题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。

第三个参数为 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。

第四个参数为 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 次询问的 题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 的集合,题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。

返回

题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 每个结点的权值。

C++

题意    在一颗有   个结点且 以  为根节点树上,起初每个结点的初始权值为  。    现在有  次操作,每次操作选择将以  为根节点的子树上的所有结点权值增加  。    求  次操作后从  到  每个结点的权值。    输入    第一个参数为 ,     第二个参数为边  的集合,其中  表示结点  与结点  之间有一条边,     第三个参数为 ,     第四个参数为  次询问的  的集合,     返回    从  到  每个结点的权值。 QuestCompleted

class Solution { public:     vector<vector<int> > AL;     vector<int> dfn, bottom, parent;     int curDfn;     void dfs(int u, int fa) {         dfn[u] = curDfn++;         parent[u] = fa;         for (const auto &v : AL[u]) {             if (v != fa) {                 dfs(v, u);             }         }     }     int dfs2(int u) {         if (bottom[u] != -1) {             return bottom[u];         }         for (const auto &v : AL[u]) {             if (v != parent[u]) {                 bottom[u] = max(bottom[u], dfs2(v));             }         }         if (bottom[u] == -1) {             bottom[u] = dfn[u];         }         return bottom[u];     }     vector<long> solve(int n, vector<Point>& Edge, int q, vector<Point>& Query) {         // write code here         vector<vector<int> >().swap(AL);         AL.resize(n+1);         for (const auto &e : Edge) {             AL[e.x].emplace_back(e.y);             AL[e.y].emplace_back(e.x);         }         vector<int>().swap(dfn);         dfn.resize(n+1);         vector<int>().swap(parent);         parent.resize(n+1);         int root = 1;         curDfn = 0;         dfs(root, -1);         vector<int>().swap(bottom);         bottom.resize(n+1,-1);         // 差分数组         vector<long> diff(n+1);         int l, r;         for (const auto &i : Query) {             l = dfn[i.x];             r = dfs2(i.x);             diff[l] += i.y;             diff[r+1] -= i.y;         }         // 还原         diff.pop_back();         for (int i = 1; i < n+1; ++i) {             diff[i] += diff[i-1];         }         vector<long> ans(n);         for (int i = 1; i <= n; ++i) {             ans[i-1] = diff[dfn[i]];         }         return ans;     } }; 
关键点: 将子树转化为区间 将维护子树各点权值转化为对维护区间
1. 建树 并确定每个点的dfs序列
2. 由于dfs序列是连续的 所以对于每棵子树 我们只需要求出子树内dfs序的最小值和最大值 即为区间的左右两端
3. 对于维护区间 线段树 ST表 差分数组都可以 此处使用差分数组 因为本题离线 并且差分数组空间复杂度和时间复杂度低于前两者
4. 通过求前缀和还原数组

今天 06:54:57 回复(0)

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

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 题意 在一颗有   个结点且 以 为根节点树上,起初每个结点的初始权值为 。 现在有 次操作,每次操作选择将以 为根节点的子树上的所有结点权值增加 。 求 次操作后从 到 每个结点的权值。 输入 第一个参数为 , 第二个参数为边 的集合,其中 表示结点 与结点 之间有一条边, 第三个参数为 , 第四个参数为 次询问的 的集合, 返回 从 到 每个结点的权值。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情