Think of this when you can answer something for a node you and want to answer the same for every node.

Imagine a tree with the “root” somewhere in the centre and edges drawn from it in both up and down directions. Nothing changes really as far as it being a root is concerned for you’ll consider every child irrespective of how you draw or visually imagine it.

The essence is to do the same for every node.

Some notation and pre-reqs

in a tree deleting the edge $u \to v$ will disconnect it into two components $C_{u}$ and $C_{v}$ ( depending on a frame of reference for parent-child ) Define $C_{u} ∣ G / uv$ as component containing u after removing the edge
$msg (u \to par (u))$ , $msg (u \leftarrow par (u))$ , message passes from node a to node b.
if you consider $u \to par (u)$ as the edge we are removing, it breaks into $C_{u}$ , $C_{par (u)}$ . $C_{u}$ is one where u can act as the “root” to $C_{u}$ . and $C_{v}$ which does not hold v is where the $par (u)$ went to.
the solution for a node is some computation denoted by $merge (\dots messages)$
to summarise $C_{u}$ is u and BELOW, $C_{par (u)}$ is above ( not inc u )

the essence

Think in terms of an arbitrary node u, $C_{u} + C_{par (u)}$ will make the whole graph. What information do u need from $C_{u}$ and $C_{par (u)}$ as messages to be able to define a merge step.

The essence is simply that you store all that and then merge.

example: tree distances 1

For each node, what is the max distance of ANY node from it.

how to think about this

what information do I need from $C_{u}$
- max dist from u in the subtree aka the “depth” in $C_{u}$
what information do I need from $C_{par (u)}$
- what is the longest path that is NOT along the $u - par (u)$ edge which is simply one in $C_{par (u)}$ - can be some other child of $par (u)$ - can move up one more step and be the longest path from there
compute $msg (u \to par (u)) \to down (u), down2 (u)$ , the top2 max paths down
compute $msg (u \leftarrow par (u)) \to up (par (u)), down_{C_{par (u)}}$ . this 2nd term can be derived from $down$ , $down2$ .
merge $for (u : G) ans (u) = max (down (u), up (u))$

implementaional aspects

Here’s what to note

down is the standard dfs
up will have this structure where you compute something in par not being -1.
final merge can just be a simple loop. some people do it in the same up dfs but that’s not a clean separation.

// problem: for each node the max distance to some other node
// tag: edge message dp
 
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	vector<vector<int>> g(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
 
	struct top2 {
		array<int, 2> tag{};
		array<int, 2> arr{};
		void add(int key, int val) {
			if (val >= arr[0]) {
				arr[1] = arr[0];
				arr[0] = val;
				tag[1] = tag[0];
				tag[0] = key;
			} else if (val > arr[1]) {
				arr[1] = val;
				tag[1] = key;
			}
		}
		array<int, 2> best() { return {tag[0], arr[0]}; }
		array<int, 2> other(int key) {
			if (key == tag[0])
				return {tag[1], arr[1]};
			return best();
		}
	};
 
	// now for split on u-v edge, we need up and down
	// now up is fine but down needs to be NOT across the u-v cut that
	// we are making
	vector<int> up(n + 1);
	vector<top2> down(n + 1);
 
	// if you fill these we can have a final MERGE step
	// this fills msg(u -> par(u))
	auto downf = [&](auto &&f, int u, int par) -> int {
		// by dfs this partition parition would be seprate
		// from parent
		auto &d = down[u];
		for (int v : g[u]) {
			if (v == par)
				continue;
			// you can think of this as the sep even
			// because re-root / messages go in both directions
			d.add(v, 1 + f(f, v, u));
			// READ AS: for u, branch v, produced this value
		}
		return d.best()[1];
	};
	downf(downf, 1, -1);
 
	// this'll fill msg( u <- par(u) )
	auto upf = [&](auto &&f, int u, int par) -> void {
		if (par != -1) {
			up[u] = 1 + max(up[par], down[par].other(u)[1]);
		}
		for (int v : g[u])
			if (v != par)
				f(f, v, u);
	};
	upf(upf, 1, -1);
 
	// MERGE, you can think of this as the "re"-root as for a node
	// I consider ALL edges similar to the root case ( par as -1 )
	for (int u = 1; u <= n; u++) {
		cout << max(up[u], down[u].best()[1]) << " ";
	}
	cout << "\n";
}

an alternate solution using diameters

for this specific problem though, we can do this which is simpler but then the point was to learn edge-message dp.

find a diamerter points pair, the farthest distance would be dist from ONE of those. Note that you can’t use the same on a generic graph even though diameter is defined for those, reason being cycles ( if it has no cycles it’s tree — assuming connected )

example: tree distances 2 ( pushing the idea to extremes )

We define

[ \text{down}(u)=\sum_{x \in subtree(u)} dist(u,x), ]

and

[ \text{up}(u)=\sum_{x \notin subtree(u)} dist(u,x). ]

Then

[ ans(u)=down(u)+up(u). ]

To compute (up(u)) from its parent (p), split the contribution into two parts.

(1) Nodes outside the subtree of (p)

Every such node is one edge farther from (u) than from (p).

[ up(p)+(n-sz(p)). ]

(2) Nodes inside the subtree of (p) but outside the subtree of (u)

Start with the contribution of the entire subtree of (p):

[ down(p). ]

Remove the contribution of the subtree of (u):

[ down(u)+sz(u), ]

since every node in the subtree of (u) contributes one extra edge to (p).

This leaves

[ down(p)-\bigl(down(u)+sz(u)\bigr). ]

Finally, every remaining node (the sibling subtrees together with (p)) is one edge farther from (u), so add

[ sz(p)-sz(u). ]

Therefore,

[ up(u)=up(p)+(n-sz(p))+\Bigl(down(p)-\bigl(down(u)+sz(u)\bigr)\Bigr)+\bigl(sz(p)-sz(u)\bigr). ]

Expanding,

[ \boxed{up(u)=up(p)+down(p)-down(u)+n-2,sz(u)} ]

since the (+sz(p)) and (-sz(p)) cancel.

implemenation

since any calcultion would be a down followed by an up dfs, you can merge the fills into the same routine

 
#include <bits/stdc++.h>
using namespace std;
 
using int = long long;
 
int main() {
	int n;
	cin >> n;
 
	vector<vector<int>> g(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
 
	vector<int> sz(n + 1);
	vector<ll> down(n + 1), up(n + 1), ans(n + 1);
 
	auto dfs_down = [&](auto &&f, int u, int par) -> void {
		sz[u] = 1;
		down[u] = 0;
 
		for (int v : g[u]) {
			if (v == par) continue;
 
			f(f, v, u);
 
			sz[u] += sz[v];
			down[u] += down[v] + sz[v];
		}
	};
 
	auto dfs_up = [&](auto &&f, int u, int par) -> void {
		for (int v : g[u]) {
			if (v == par) continue;
 
			up[v] =
				up[u]
				+ (n - sz[u])
				+ 1
				+ (down[u] - down[v] - sz[v])
				+ (sz[u] - sz[v] - 1);
 
			f(f, v, u);
		}
	};
 
	dfs_down(dfs_down, 1, -1);
	dfs_up(dfs_up, 1, -1);
 
	for (int i = 1; i <= n; i++) {
		ans[i] = down[i] + up[i];
        cout<< ans[i] << " ";
	}
	cout << "\n";
}

a more “re-rooting” like solution

and this is where we move away from a traditional “edge-message” idea and move to what feels more like actually “re-rooting” the tree.

The idea is based on

finding the solution with root as 1
update the original answer by applying deltas to it as you move in a dfs and “re-root” to the current node by observing that would be delta from prev root to cur node being new root.

Now both being mathematically equivalent since they are computing the same thing — it’s still quite hard to go from one to the other. Arriving to the solution and thinking involved is COMPLETELY different here.

In this case, you would define a recurrence in terms of $an s$ itself.

Assume I know $an s (p a r_{u})$ , and I want to define $an s (u)$ in terms of it and some other known $f (u)$ s.

for the case of tree distance 2

you would still need to consider the spit alone $e_{u, p_{u}}$

for paths ending in $C_{u}$ , $- sz (u)$ as each decreases by 1. for ones ending in $C_{p_{u}}$ , $n - sz (u)$ as each increases by 1.

so the final recurrense looks like

[ ans(u)=ans(p)+n-2sz(u) ]

implementation

a clean recurrence will make for a really simple implementation but the ideas of edge message vs this are both really really different

#include <bits/stdc++.h>
using namespace std;
 
int main() {
#define int long long
	int n;
	cin >> n;
	vector<vector<int>> g(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
 
	vector<int> sz(n + 1);
	int ans1 = 0; // for 1 as root
	auto f = [&](auto &&f, int u, int par, int d) -> int {
		ans1 += d;
		auto &a = sz[u] = 1;
		for (int v : g[u])
			if (v != par)
				a += f(f, v, u, d + 1);
		return a;
	};
 
	f(f, 1, -1, 0);
 
	vector<int> ans(n + 1);
	ans[1] = ans1;
 
	// I need to fill it in dfs order
	auto f2 = [&](auto &&f, int u, int par) -> void {
		if (par != -1) {
			ans[u] = ans[par] + n - 2 * sz[u];
		}
		for (int v : g[u])
			if (v != par)
				f(f, v, u);
	};
	f2(f2, 1, -1);
 
	for (int i = 1; i <= n; i++)
		cout << ans[i] << " ";
	cout << "\n";
#undef int
}

I hope and pray I won’t be “re-learning” this all from scratch ever again, for if I do I would’ve failed my present self.

Lest I Forget

Edge message dp on trees ( aka Re-rooting )