Although i understood the solution given in usaco guide but still i cannot convince myself why the following statement always produce correct result?
Direct all edges that aren't part of this tree "upwards".
i’ve already read the cf blog given in guide but still cannot get intuition behind this.
Any help would be appreciated.
relevent code
void dfs(int u,int p){
vis[u] = timer++;
trav(v,adj[u]){
if(v==p) continue;
if(vis[v]!=-1){
if(vis[v] <= vis[u]){ // check if it is backedge that is going from child to its ancestor
odd[u] =odd[u]^1;
ans.push_back(mp(u,v)); // assign upward edge why?
}
}
else{
dfs(v,u);
if(odd[v]) {ans.push_back(mp(v,u)); odd[v]=0;}
else{ ans.push_back(mp(u,v)); odd[u] =odd[u]^1;}
}
}
}