【HihoCoder - 1881】特殊任务 （树形图，遍历）

题干：

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代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #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; vector<int> vv[MAX]; ll a[MAX]; ll maxx; pair<ll,ll> dfs(int cur,int root) {int up = vv[cur].size();ll tmp,TMP;tmp=TMP=a[cur];for(int i = 0; i<up; i++) {int v = vv[cur][i];if(v == root) continue;pair<ll,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;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i);for(int i = 2; i<=n; i++) {int x;scanf("%d",&x);vv[i].pb(x);vv[x].pb(i);} // if(n == 1) { // puts("0");return 0 ; // }pair<ll,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、、、还是要注意一下子节点（所有子树）和单个子树的区别吧

总结

以上是生活随笔为你收集整理的【HihoCoder - 1881】特殊任务 （树形图，遍历）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。