fork download
copy 
  1. /*input
  2. 5
  3. 3 10 6 7 9
  4. 1
  5. 1
  6. 3
  7. 3
  8.  
  9. */
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12. const int N=5e5 + 10;
  13. #define int long long
  14. vector<int> adjlist[N];int n, arr[N], dp1[N][51], dp2[N][51];//1 is strictly increasing at most j, 2 is strictly decreasing at least j.
  15. int ans;
  16. void dfs(int i){
  17. 	int ct=0;
  18. 	for(int j=0;j<51;j++) dp1[i][j]=dp2[i][j]=0;
  19. 	for(auto j:adjlist[i]){
  20. 		dfs(j);
  21. 		for(int k=1;k<51;k++)
  22. 		{
  23. 			dp1[i][k]=max(dp1[i][k], dp1[j][k]);
  24. 			if(k==arr[i]) dp1[i][k]=max(dp1[i][k], dp1[j][k-1] + arr[i]);
  25. 			dp2[i][k]=max(dp2[i][k], dp2[j][k]);
  26. 			if(k==arr[i])
  27. 			{
  28. 				if(k==50) dp2[i][k]=50;
  29. 			 	else dp2[i][k]=max(dp2[i][k], dp2[j][k+1] + arr[i]);
  30. 			}
  31. 		}
  32. 	}
  33. 	if(adjlist[i].empty()) dp1[i][arr[i]]=dp2[i][arr[i]]=arr[i];
  34.  
  35. 	for(int k=2;k<51;k++)
  36. 	{
  37. 		dp1[i][k]=max(dp1[i][k], dp1[i][k-1]);
  38. 	}
  39. 	for(int k=49;k>0;k--)
  40. 	{
  41. 		dp2[i][k]=max(dp2[i][k], dp2[i][k+1]);
  42. 	}
  43. 	for(int j=0;j<51;j++)
  44. 	{
  45. 		if(j==50) ans=max(ans, dp1[i][j]);
  46. 		else ans=max(ans, dp1[i][j] + dp2[i][j+1]);
  47. 	}
  48. }
  49. signed main()
  50. {
  51. 	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  52. 	//freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  53. 	cin>>n;
  54. 	for(int i=1;i<=n;i++)
  55. 	{
  56.     cin>>arr[i];
  57. 	}
  58. 	for(int i=1;i<n;i++)
  59. 	{
  60. 		int p;cin>>p;
  61. 		adjlist[p].push_back(i+1);
  62. 	}
  63. //	cout<<"ok";
  64. 	ans=0;
  65. 	dfs(1);
  66. 	cout<<ans;
  67. }
Success #stdin #stdout 0s 429312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sKpbuv
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!