CSES - Tree Distances I

Solution 1

Described in CPH 14.3.

// source -> https://cses.fi/problemset/task/1132/

#include<bits/stdc++.h>
using namespace std;

// GCC Optimizations
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

Solution 2

Compute a diameter of the tree as described by algorithm 2 here. Once we have a diameter $(a,b)$, output $\max(dist(a,i),dist(b,i))$ for each node $i$.

#include <bits/stdc++.h>

using namespace std;

// dist[0][i] = distance from node a to node i
// dist[1][i] = distance from node b to node i
int dist[2][200000];
vector<int> adj[200000];

int dfs(int u, int p, int d, int i) {