asp网站源码使用,机票网站手机版建设,百度seo排名优化联系方式,湖南建设厅网站勘查设计题干#xff1a;
H公司一共有N名员工#xff0c;编号1~N#xff0c;其中CEO是1号员工。除了CEO之外#xff0c;其他员工都有唯一的直接上司#xff0c;所以N名员工上下级关系恰好形成了一棵树形结构。
我们知道每一名员工向H公司的代码库贡献了多少行代码。具体来说
H公司一共有N名员工编号1~N其中CEO是1号员工。除了CEO之外其他员工都有唯一的直接上司所以N名员工上下级关系恰好形成了一棵树形结构。
我们知道每一名员工向H公司的代码库贡献了多少行代码。具体来说第i名员工贡献了Ai行代码。
现在有一项特殊的任务需要2名员工完成这两名员工需要满足
1. 其中一名是另一名的直接或者间接上司
2. 两人贡献代码行数的差值越大越好
请你在所有员工中找出符合条件的2人输出他们代码行数的差值。
Input
第一行包含一个整数N。
第二行包含N个整数A1, A2, ... AN。
以下N-1行每行包含一个整数依次是P2, P3, ... PN其中Pi代表第i名员工的上司编号。
对于30%的数据1 ≤ N ≤ 1000
对于100%的数据1 ≤ N ≤ 100000, 0 ≤ Ai ≤ 100000, 1 ≤ Pi ≤ N
Output
一个整数代表答案
Sample Input
6
50 70 100 40 20 0
1
1
2
4
4
Sample Output
70解题报告 这题思路有如下几种法一dfs序线段树但是这题没有更新所以就没必要。法二直接遍历这棵树。其次这题没说清楚啊n等于1是什么鬼不是让选两个人吗特判了一下但是加不加那一句都可以AC貌似样例中就没有这个样例
简单介绍一下变量的含义
pair的mM分别代表最小值 最大值 tmp是所有子树的最小值 TMP 是所有子树的最大值 pair是单个子树带回的最大值最小值
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX 2e5 5;
vectorint vv[MAX];
ll a[MAX];
ll maxx;
pairll,ll dfs(int cur,int root) {int up vv[cur].size();ll tmp,TMP;tmpTMPa[cur];for(int i 0; iup; i) {int v vv[cur][i];if(v root) continue;pairll,ll mM dfs(v,cur);tmp min(tmp,mM.fi);TMP max(TMP,mM.se);//maxx max(maxx,max(mM.se,a[cur]) - min(mM.fi,a[cur]));maxx max(maxx,abs(mM.second-a[cur]));maxx max(maxx,abs(mM.first-a[cur]));}return pm(tmp,TMP);
}
int main()
{int n,m;cinn;for(int i 1; in; i) scanf(%lld,ai);for(int i 2; in; i) {int x;scanf(%d,x);vv[i].pb(x);vv[x].pb(i);}
// if(n 1) {
// puts(0);return 0 ;
// }pairll,ll mM dfs(1,-1);printf(%lld\n,maxx);return 0 ;}/*
5
11 10 20 3 10
1
2
1
4*/
总结 遍历的时候刚开始还是出错了。。。不能直接用tmp和TMP去更新maxx因为每棵子树得分开算并且维护一个tmp和TMP返回给父节点。。然后不能用那个注释掉的那个maxx的更新因为你只能用带回来的值去和a[cur]去做运算不能直接在这两者中选一个大的两者中选一个小的去做运算来维护maxx、、、还是要注意一下子节点所有子树和单个子树的区别吧
