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.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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);↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
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.↵
↵
[problem:1859F]
↵
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.↵
↵
<spoiler summary="Code">↵
↵
~~~~~↵
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);↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
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.↵
↵
[problem:1859F]
