ppt设计公司/短视频排名seo
对于二叉树，一般认为其遍历可以委派到左右子树的遍历。同理，对于树结构，其可以委派到其所有子节点的遍历。
vector<node*> next 用于描述其所有子节点的指针题目描述
牛牛有一个算法交流群，它是这个群的群主，也是这个群实力最强的人。
算法交流群里一共有n个人，每个人都有一个等级a_iai表示它能解决难度小于等于a_iai的算法问题。
除了牛牛以外，群里的每个编号为i的人都在群里有一个等级比他高的朋友编号为p_ipi。群友 i 会解决那些他产生和接收的等级小于等于a_iai的问题，并把解决不了的问题全部交给p_ipi。
保证牛牛的编号为1。保证牛牛的等级全场唯一且全场最高。如果牛牛解决不了他接收的问题，他将不管这些问题。
这天群里的每个人都产生了一个问题，牛牛知道了每个人产生问题等级k_iki，他想知道群里的每个人在这天解决了多少问题。
示例1
输入
复制
4,[4,3,2,1],[1,2,3],[1,2,3,4]
输出
复制
[2,2,0,0]
说明
群里一共有4个人
4产生了等级为4的问题，4的能力值为1，无法解决，所以4号把这个问题交给了3号.4号解决问题个数为0
3号产生了等级为3的问题，接受到等级为4的问题。3号本身等级为2，无法解决这两个问题，于是把这两个问题交给了2，自身解决问题个数为0.
2号产生了等级为2的问题，接受到等级为3，4的两个问题。2号等级为3，解决了等级为2，3的问题，把等级为4的问题交给了1.自身解决问题个数为2
1号产生了等级为1的问题，接受到等级为4的问题。1号自身等级为4，解决了这两个问题。自身解决问题个数为2
备注:
输入的第一个参数为整数n，代表群人数
输入第二个参数为vector<int> a，包含n个元素，按顺序代表每个人的等级
输入的第二个参数为vector<int> p，包含n-1个元素，按顺序代表2,3,...n号群友会找谁寻求帮助
输入的第三个参数为vector<int> k，包含n个元素按顺序代表每个人产生的问题等级
【思路一】 常规DFS ：从根节点开始，不断进入DFS 叶子节点开始返回，依次解决问题，并返回不能解决的问题集合
vector<int> dfs(int who)
返回who节点不能解决的问题集合（包含自身不能解决，以及被子节点委派的问题集合） map<int,vector<int>> mp;//mp[i]表示 i是哪些人的上级（即 i 是vector<int> 的父节点）vector<int> arr;vector<int> dfs(int who,const vector<int>&a ,const vector<int>& k ) //返回who节点不能解决问题的等级组合{vector<int> cannot_solve;//不能解决的问题集合//先查看自身的问题能否解决if(a[who]>=k[who]) //能够解决自身问题arr[who]++;else{cannot_solve.push_back(k[who]);//添加进不能解决集合}if(mp.find(who)==mp.end()) //没有子节点return cannot_solve; // 子节点返回的那些不能解决列表for(int i=0;i<mp[who].size();i++){vector<int> child_cannot_solve=dfs(mp[who][i],a,k);for(auto item:child_cannot_solve){if(a[who]>=item)arr[who]++;elsecannot_solve.push_back(item);//不能解决 添加进不能解决列表}}return cannot_solve; }vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {// write code herefor(int i=0;i<n;i++)arr.push_back(0);//初始化 每个人能解决的问题数量为0for(int i=0;i<p.size();i++){int father=p[i];// 第i+2 位的父节点是 p[i]mp[father-1].push_back(i+1);//注意这里 每个人序号从1开始} dfs(0,a,k);//从根节点开始 也就是能力最强的选手开始return arr;}
对于本问题，采取dfs做法，在存在大量节点时，将存在大量的vector<int> 拷贝，以及递归函数调用带来的开销。
【思路二】 采取循环的方式
vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k) {// write code herevector<int> res(n,0);//存放结果for(int i=0;i<k.size();i++) //分析每一件任务{if(k[i]>a[0]) //最强的人也无法解决continue;else if(k[i]==a[0]) //只能最强的人解决{res[0]++;}else{int j=i; //分析第i个任务被谁解决 while(a[j]<k[i]) // 依次向父节点委派 找到能解决的人jj=p[j-1]-1;//下标从1开始res[j]++;//由第j个人解决}}return res;}
时间复杂度分析：
最优：每个人都独自解决 O（N）
最差：每个人都委派到根节点 O（N*N）