My friend sent me this question along with the code and he needs my help in reverse engineering as to what is actually happening in this code.
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
const int N = 1e5+4, ninf = -2e5;
const int inf = 2e5;
int in[N], out[N], mark[N];
vector<int> adj[N];
void dfs(int src, int par){
if (!mark[src])
in[src] = ninf;
else
in[src] = 0;
for(int child : adj[src]){
if (child == par) continue;
dfs(child, src);
in[src] = max(in[src], 1+in[child]);
}
}
void dfs1(int src, int par){
int a1 = ninf, a2 = ninf;
for(int child : adj[src]){
if (child == par)continue;
if (in[child] >= a1){
a2 = a1;
a1 = in[child];
}
else if (in[child] > a2)
a2 = in[child];
}
int use;
for(int child : adj[src]){
if (child == par)
continue;
use = a1;
if (a1 == in[child])
use = a2;
out[child] = max(2+use, 1+out[src]);
if (mark[child] && out[child]<0)
out[child] = 0;
dfs1(child, src);
}
}
void solve(){
int n,k,r;
cin >> n >> k >> r;
for(int i = 1; i <= n; i++){
mark[i] = 0;
adj[i].clear();
}
for(int i = 0; i < k; i++){
int x;
cin >> x;
mark[x] = 1;
}
for(int i = 0; i < n-1; i++){
int x,y;
cin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 0);
out[1] = ninf;
if (mark[1])
out[1] = 0;
dfs1(1, 0);
int ans = 0;
for(int i = 1; i <= n; i++){
if(in[i] <= r && out[i] <= r)
ans++;
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
return 0;
}
Questions:
- What is the use of the arrays in[N] and out[N] ?
- What is going on in dfs() and dfs1() functions ?
- I know that “a1” and “a2” represent the largest and the second largest value of the “in value” of the children of a given node but what is the use of these 2 variables?