Explanation

Let $a$, $b$, and $t$ be the nodes given in each query, and $p$ be the LCA of $a$ and $b$. Directly updating the path from $a$ to $b$ is difficult to do, so breaking up the path into smaller segments is necessary. To do that, we use some casework.

Case 1: $p$ is equal to $t$, or $t$ is not inside $p$'s subtree.

In this case, we update the path from $a$ to $p$ and $b$ to $p$. Note that if $p$ is equal to either $a$ or $b$, then this case must be handled slightly differently.

Case 2: $p$ is equal to either $a$ or $b$.

Let the first ancestor of $t$ that is on the path from $a$ to $b$ be $l$. WLOG, let $b$ be equal to $p$. Then, we update the path from $a$ to $l$ and the path from $l$ to $b$.

Case 3: The LCA of $t$ with $a$ and $b$ is the same as $p$.

Like how we handled case 1, for this case we update the path from $a$ to $p$ and the path from $b$ to $p$.

Case 4: Either the LCA of $t$ and $a$ or the LCA of $t$ and $b$ lie on the path from $a$ to $b$.

In this case, split the path updates into 3 segments. Let the lower of the two LCAs mentioned be $l$, and the node which is an ancestor of $l$ be $a$. Then, just update the path from $a$ to $l$, $l$ to $p$, and the path from $b$ to $p$.

Handling Path Updates

Note that based on how we did our casework on the paths, that all path updates are between a given node and its ancestor. Also, note that the path updates are just adding distances which either increase or decrease by a fixed amount every time. So, we can sort of do a difference array on a tree, where we DFS down the tree and apply the differences while walking back up the tree.

Implementation

Time Complexity: $\mathcal{O}(N\log{N})$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class Tree {
  private:
	const int n;
	const int log2dist;         // # of bits needed for binary lift
	vector<vector<int>> &adj;   // reference to adjacency list
	vector<vector<int>> lift;   // for binary lifting