~~~~~
[Question link ](https://codeforces.me/contest/1997/problem/D)↵
↵
[tutorial link](https://codeforces.me/blog/entry/132154)↵
↵
my code:-↵
↵
~~~~~↵
#include <iostream>↵
#include <math.h>↵
#include <map>↵
#include <utility>↵
#include <vector>↵
#include <set>↵
#include <string.h>↵
#include <stdlib.h>↵
#include <algorithm>↵
#include <functional>↵
#include <queue>↵
#include <stack>↵
#include <iomanip>↵
#include <numeric>↵
#include <bitset>↵
#include <cstdio>↵
↵
using namespace std;↵
typedef long long int ll;↵
typedef vector<ll> vl;↵
typedef pair<ll,ll> pl;↵
typedef bitset<64> bl;↵
typedef unsigned long long int llu;↵
typedef priority_queue<ll> pq;↵
↵
#define rep(i, n) for (ll i = 0; i < n; i++)↵
#define repr(i, n) for (ll i = n-1; i >=0 ; i--)↵
#define repe(i, n) for (ll i = 0; i <= n; i++)↵
#define sortv(v) sort(v.begin(), v.end())↵
#define O cout <<↵
#define I cin >>↵
#define F first↵
#define S second↵
#define PB push_back↵
↵
ll inf=1e9;↵
map<ll,vl> mptree;↵
map<ll,ll> mp;↵
↵
bool dns(ll n,ll val){↵
if(mptree[n].size()==0 ){↵
if(mp[n]>=val){↵
return true;↵
}else{↵
return false;↵
}↵
}↵
for(auto &i:mptree[n]){↵
if(mp[i]<val){↵
if( (val+val-mp[i])>inf || !dns(i,(val-mp[i]))){↵
return false;↵
}↵
}else if(mp[i]>=val){↵
if(!dns(i,val)){↵
return false;↵
}↵
}↵
}↵
return true;↵
}↵
↵
ll solve()↵
{↵
ll n;↵
I n;↵
vl arr(n);↵
rep(i,n){↵
I arr[i];↵
mp[i+1]=arr[i];↵
}↵
rep(i,n-1){↵
ll x;↵
I x;↵
mptree[x].push_back(i+2);↵
}↵
ll answer=0;↵
ll l=0,r=1e9;↵
while(l<=r){↵
ll mid=l+(r-l)/2;↵
if(dns(1,mid)){↵
answer=mid;↵
l=mid+1;↵
}else{↵
r=mid-1;↵
}↵
}↵
return answer+arr[0];↵
}↵
↵
int main()↵
{↵
// for input output files↵
// freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵
↵
// Bit manipulation↵
// __builtin_clz(x): the number of zeros at the beginning of the bit representation↵
// __builtin_ctz(x): the number of zeros at the end of the bit representation↵
// __builtin_popcount(x): the number of ones in the bit representation↵
// __builtin_parity(x): the parity (even or odd) of the number of ones in the bit representation ↵
↵
ll t;↵
cin >> t;↵
while (t--)↵
{↵
O solve()<<"\n";↵
mp.clear();↵
mptree.clear();↵
}↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
