DFS

#include <bits stdc++.h="">
using namespace std;
#define ll long long
#define ld long double
const int M = 1e9 + 7;
const ll MAX_WATER_IN_CITY = 1e18+1;

int n, s, *cap;
bool overDemand = false;
vector<vector<int>> e;
bool vis[100001];
ll int maxReq(int node){
ll int max=0;int c=0;vis[node]=true;
for(auto x:e[node]){
if(!vis[x]){c++;
ll int t=maxReq(x);max=max>t?max:t;}
}
ll int ans = cap[node] + max*c;
if (ans > MAX_WATER_IN_CITY || ans < 0) {
overDemand = true;
return 0; }
return ans; }

int main()
{
int t = 0;
cin >> t;
while (t--)
{
cin >> n >> s;
s--;memset(vis,false,n);
cap = new int[n + 1];
e.clear();
e.resize(n + 1, vector<int>());
for (int i = 0; i < n; i++)
{
cin >> cap[i];
}
for (int i = 0; i < n - 1; i++)
{
int x, y;
cin >> x >> y;
x--;
y--;
e[x].push_back(y);
e[y].push_back(x);
}
ll int ans = maxReq(s);
overDemand ? cout << -1 << endl : cout << ans << endl;
}
return 0;
}