#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define vi vector
#define pii pair<int,int>
#define pb push_back
#define forn(x,n) for(int x = 0; x < n; ++x)
#define deb(x) cout<<#x<<" “<<x<<”\n";
#define w(q) int q ; cin>>q; while(q–)
vectora;
vector adj;
int n,x;
pii dfs(int u , int parent = - 1){
int sum = a[u] ;
int deleted = 0;
for(auto v : adj[u]){
if(v!= parent){
pii p = dfs(v,u);
sum += p.first;
deleted += p.second;
}
}
pii p = make_pair(sum,min(deleted,x+sum));
return p;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
w(t){
cin>>n>>x;
a.resize(n+1);
adj.resize(n+1);
forn(i,n)cin>>a[i+1];
forn(i,n-1){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
pii p = dfs(1);
int total = p.first;
int deleted = min(p.second,total+x);
int ans = total - deleted;
cout<<ans<<"\n";
}
return 0;
}
This solution is giving TLE , There is one dfs per test case, couldn’t debug.
Please somebody look into it.
Thanks