Hi everyone!

This is a pretty basic blog about dp on trees, nothing advanced. Like always, I write blogs about something which I found both not obvious while solving the problem and it's a general idea which can be used in other problems.

The problem is as follows:

A weighted tree on $$$n$$$ vertices is given, as well as $$$n$$$ values $$$d_v$$$. The task is to run Dijkstra algorithm with these initial values. Usual setup for Dijkstra is $$$d_v = \infty$$$ and $$$d_{root} = 0$$$, but here all vertices have a start value. We need to do that in $$$O(n)$$$.

Solution: Root the tree arbitrarily. All pathes in a tree look like first going up and then going down. We'll do two dfs-es, the first will relax values from children to vertex, the second will relax values from vertex to children. This way every shortest path is accounted.

using ll = long long;
using pii = pair<int, int>;

vector<pii> g[N];
ll dist[N];

void dfsUp(int v, int pr = -1) {
    for (auto &[u, w] : g[v])
        if (u != pr) {
            dfsUp(u, v);
            dist[v] = min(dist[v], dist[u] + w);
        }
}

void dfsDown(int v, int pr = -1) {
    for (auto &[u, w] : g[v])
        if (u != pr) {
            dist[u] = min(dist[u], dist[v] + w);
            dfsDown(u, v);
        }
}

If we need to run a single Dijksta, $$$O(n \log n)$$$ gets TLE rarely, where $$$O(n)$$$ works. But if we need to run many Djikstras, for example, in binary search or in centroid decomposition, this will give a big speed up.

The problem where this optimisation is used is below, though it's not the hardest part of the problem.

1859F - Teleportation in Byteland