Hey everyone I was recently solving Tree Distances-1 from CSES DP on Trees - Solving For All Roots I was able to get the editorial posted here. Which says about h(x) and g(x)
What all I am getting from editorial is
- ans[x]=max(f(x),g(x))
What I am not getting from editorial is code present there mainly these two dfs functions doubts mainly I have is
void dfs1(int node = 1, int parent = 0) {
for (int i : graph[node])
if (i != parent) {
dfs1(i, node);
if (fir[i] + 1 > fir[node]) {
sec[node] = fir[node];
fir[node] = fir[i] + 1;
} else if (fir[i] + 1 > sec[node]) {
sec[node] = fir[i] + 1;
}
}
}
Can some one explain me what is fior and sec and how and why they are been updated like given
void dfs2(int node = 1, int parent = 0, int to_p = 0) {
ans[node] = max(to_p, fir[node]);
for (int i : graph[node])
if (i != parent) {
if (fir[i] + 1 == fir[node])
dfs2(i, node, max(to_p, sec[node]) + 1);
else dfs2(i, node, ans[node] + 1);
}
}
Also how ans is getting been calculated from here
I want to get explaintaion of these 2 functions