How does the findparent function works

#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";
}

}

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

Blog on Tree Basics by Second Thread

1 Like