Distances

#include <bits/stdc++.h>
 
using namespace std;
 
vector<vector<int>> adj; 
vector<int> depth; 
vector<int> leaf; 
void dfs(int node, int par){
	depth[node] = depth[par] + 1; 
	for(int v : adj[node]){
		if(v == par) 
			continue; 
		dfs(v, node);
	}
	if(adj[node].size() == 1 && node != 0)
		leaf[node] = 1; 
}
 
vector<int> ans; 
 
void dfs2(int node, int par){
	if(leaf[node] == 1 || (depth[node] & 1) == 0)
		ans.push_back(node); 
	 for(int v : adj[node]){
	 	if(v == par)
	 		continue; 
	 	dfs2(v, node); 
	 }
	 if((depth[node]&1) && !leaf[node])
	 	ans.push_back(node); 
}
void solve(){
	adj.clear(); 
	ans.clear();
	int n;
	cin >> n; 
 
	adj.resize(n); 
	for(int i = 0; i < n-1; i++){
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u); 
	}
	depth.assign(n, 0); 
	depth[0] = -1; 
	leaf.assign(n, 0); 
	dfs(0, 0);
 
	dfs2(0, 0); 
 
	for(int v : ans)
		cout << v+1 << ' '; 
	cout << '\n';
}
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int t;
	cin >> t; 
 
	for(int tc = 0; tc < t; tc++)
		solve(); 
	return 0; 
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED