In this HackerEarth Zero path operations problem solution Given a tree with N nodes with some non-negative value assigned to it. Let's say that the value of the ith node is wi. The beauty of a path between nodes u and v (denoted by B(u,v)) is described as the sum of values of all nodes that lie on the path excluding the nodes u and v. Note that B(u,v) is always zero for any valid node u. Ash is a weird guy. He only likes trees that have Sigma(u=1,N) Sigma(v=1,N) B(u,v) = 0. In one operation Ash can change the value of any node to any non-negative value. Ash wants to find the minimum number of operations required so that he starts liking the given tree. But Ash does not have time to solve the problem as he is on his Pokemon adventure. So he needs your help in solving this problem.

HackerEarth Zero path operations problem solution


HackerEarth Zero path operations problem solution.

#include<bits/stdc++.h>
using namespace std;
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
/*template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;

#define int ll
#define LOCAL 0
#define dbg(x) cout << #x << " is " << x << "\n"
#define gll(x) scanf("%d",&x)
#define gll2(x,y) scanf("%d%d",&x,&y)
#define gll3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define gllarr(arr,n) f(i,n) gll(arr[i]);
#define sz(x) ((int)x.size())
#define s(x) sort(x.begin(),x.end())
#define all(v) v.begin(),v.end()
#define rs(v) { s(v) ; r(v) ; }
#define r(v) {reverse(all(v));}
#define pb push_back
#define f(i,n) for(int i=0;i<n;i++)
#define fr(i,n) for(int i=n-1;i>=0;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e16;
const ld eps = 1e-12;
const ll N = (int)1e5 + 5;
const ll LOGN = 19;
const ld PI = 3.14159265358979323846;
inline ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
inline ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
inline ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}

int a[N], deg[N];

int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (LOCAL) {
freopen("C:\\Users\\Collection-DEV c++\\input.txt", "r", stdin);
freopen("C:\\Users\\Collection-DEV c++\\output.txt", "w", stdout);
}
int t;
cin>>t;
assert(t >= 1 && t <= 10);
while(t--) {
int n;
cin>>n;
assert(n >= 1 && n <= (int)1e5);
memset(deg, 0, sizeof(deg));
f(i, n - 1) {
int u, v;
cin>>u>>v;
assert(u >= 1 && u <= n);
assert(v >= 1 && v <= n);
u--, v--;
deg[u]++;
deg[v]++;
}
f(i, n) {
cin>>a[i];
assert(a[i] >= 0 && a[i] <= (int)1e9);
}
if(n == 1) {
cout<<"0\n";
continue;
}
int ans = 0;
f(i, n) {
assert(deg[i] > 0);
if(deg[i] == 1) continue;
if(a[i] != 0) ans++;
}
cout<<ans<<"\n";
}
int junk;
assert(!(cin>>junk));
return 0;
}