 # How does the findparent function works

#define int long long

int visited;
int values, parent;

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, 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;
visited[i] = 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] == 1){
continue;
}
dfs(x, 0, tree, x, parent[x]);
visited[x] = 1;

}

for(i=0; i<n; i++){
cout << values[i] << " ";
}
cout << "\n";
}
``````

}

It is just creating a parent array while doing a basic dfs.

1 Like

@mafailure can u share a link where how to take input and process input on tree is explained

1 Like