-
link to problem : CodeChef: Practical coding for everyone
-
solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
int visited[200005][2];
int values[200005], parent[200050];
void dfs(int vertex, int parity, vector tree[], int source, int parent){
//if the vertex is not source and distance from source is even add the value
if(vertex != source && parity == 0){
values[source] += values[vertex];
values[vertex] = 0;
}
//if visited[vertex][1] == 1, all the nodes at odd distance
//from the current vertex are zero. So there is no need to go further.
if(visited[vertex][parity] == 0){
for(auto x: tree[vertex]){
if(x != parent){
//if we are looking for nodes at an even distance from current node,
//then we have to look for nodes at an odd distance from this node's children
dfs(x, parity^1, tree, source, vertex);
}
}
//if parity == 1, all nodes at odd distance from this vertex have been visited
//if parity == 0, all nodes at even distance from this vertex have been visited
visited[vertex][parity] = 1;
}
}
void findParents(int v, vector tree[], int par){
parent[v] = par;
for(auto x: tree[v])
if(x != par)
findParents(x, tree, v);
}
int32_t main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
int t;
cin >> t;
while(t--){
int n, i, j, x, u, v, q;
cin >> n >> q;
for(i=0; i<200005; i++){
visited[i][0] = 0;
visited[i][1] = 0;
}
// take the input values
for(i=0; i<n; i++)
cin >> values[i];
//take the input tree
vector<int> tree[n];
for(i=0; i<n-1; i++){
cin >> u >> v;
u--; v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
// find the parent of each vertex
findParents(0, tree, -1);
while(q--){
cin >> x; x--;
if(visited[x][0] == 1){
continue;
}
dfs(x, 0, tree, x, parent[x]);
visited[x][0] = 1;
}
for(i=0; i<n; i++){
cout << values[i] << " ";
}
cout << "\n";
}
}