🗂️Data StructureAdvanced

Top Tree

Key Points

•
Top trees are dynamic tree data structures that represent a forest as a hierarchy of clusters, allowing O(log n) amortized time for link, cut, path queries/updates, and many subtree queries.
•
They generalize Link–Cut Trees by explicitly supporting rake (attach off-path subtrees) and compress (merge along a path) operations on clusters.
•
Every query like “sum/max on a path” or “sum in a rooted subtree” is answered by recursively merging cluster summaries instead of walking nodes.
•
A splay-based implementation can realize a top tree, where access exposes a preferred path and rakes all other incident subtrees into virtual aggregates.
•
Path updates can be done lazily on the exposed splay path, while subtree queries rely on virtual (raked) aggregates kept at boundaries.
•
The design forces you to separate two kinds of aggregates: on-path (preferred-path cluster) and off-path (virtual/raked cluster) values.
•
With careful lazy propagation and bookkeeping of virtual aggregates, you obtain O(log n) amortized performance and low constant factors.
•
Top trees shine in advanced problems where both path and subtree operations must coexist under fully dynamic link/cut changes.

Prerequisites

→Heavy–Light Decomposition — Provides intuition for decomposing a path into a few segments and for designing associative path aggregates.
→Splay Trees — Top trees are often implemented with splay trees; understanding rotations and amortized analysis is essential.
→Link–Cut Trees — Top trees generalize link–cut ideas; knowledge of expose (access), make_root, and path aggregates helps a lot.
→Lazy Propagation — Path updates rely on lazy tags pushed through auxiliary trees.
→Amortized Analysis — Explains why operations run in O(log n) on average using potential functions.
→Tree Basics (LCA, paths, subtrees) — You must be comfortable with path and subtree definitions and rooted vs. unrooted views.
→Associative Aggregates — Path/subtree combinations require well-defined merge functions that are associative or carefully oriented.

Detailed Explanation

Tap terms for definitions

01Overview

A top tree is a powerful dynamic tree data structure for maintaining a changing forest under link (add edge), cut (remove edge), and a rich set of queries/updates on paths and subtrees, all in O(log n) amortized time. The central idea is to represent parts of the tree—called clusters—recursively. A cluster is a connected subgraph with one or two boundary vertices. Two basic merge operations maintain and rebuild this cluster hierarchy during queries: compress, which merges two clusters along a path, and rake, which attaches an off-path subtree to a path cluster. Because every cluster stores a small summary (like sum, min, max, xor, or more complex custom information), answers to queries are produced by combining a logarithmic number of cluster summaries instead of traversing many nodes.

From an implementation perspective, you usually realize a top tree with a balanced search tree (commonly, splay trees) that dynamically exposes a preferred path between any two vertices. During the expose, everything not on that path gets “raked” into virtual aggregates so that the path becomes a single chain for fast range operations. This approach generalizes Link–Cut Trees: if you only ever compress along preferred paths, you obtain a link–cut; adding raking of the off-path parts essentially upgrades it into a top tree. The extra bookkeeping enables efficient subtree queries and, with additional tags, some subtree updates. Top trees are widely used in high-end competitive programming and algorithmic research when you need fast updates and queries on trees that change over time.

02Intuition & Analogies

Imagine managing a large road network of cities (vertices) connected by roads (edges). Often you don’t care about every city; you care about summaries: total toll on a route, the maximum altitude along a route, or the total population inside a city’s influence zone (its subtree). If you could pre-package meaningful chunks of the map—routes between important junctions and the collections of side streets hanging off those routes—you could answer questions by combining a handful of these packages instead of scanning entire neighborhoods.

That’s what a top tree does. It wraps parts of the tree into boxes (clusters). Each box has either one or two “doors” (boundary vertices) where it connects to the rest. Two operations manage these boxes:

Compress: glue two route-boxes end-to-end to make a longer route-box.
Rake: stick a side-street box to a main route-box at one door, recording its contribution separately as a “virtual” add-on.

When you ask for a path query between u and v, the data structure rearranges boxes so that the unique u–v path becomes a neat chain of a few big boxes. Everything branching off the path is raked into virtual add-ons so they don’t clutter the chain. Now combining summaries is fast. For a subtree query of node x (with respect to a chosen root), the structure exposes x and treats the entire component below x as the “raked mass” at x, so the answer is simply “what’s on x plus its virtual add-ons.” Lazy updates (like add +5 to all cities on u–v) become “stamp the chain’s boxes with +5,” while side streets remain untouched—exactly what you want for path-only updates. This packaging-and-raking viewpoint is the key mental model: bring the path to the top, rake away the rest, and combine a few summaries.

03Formal Definition

A top tree maintains a forest G = (V, E) as a rooted hierarchy of clusters. A cluster C is a connected subgraph with at most two boundary vertices (its interface to the outside). There are two merge operators: - Compress: If clusters A and B share exactly one boundary vertex and the union A ∪ B forms a simple path whose set of boundary vertices has

s i ze \leq 2

, we may merge them into a path cluster. - Rake: If a cluster S is a subtree attached to a path cluster P at a single boundary vertex, S can be raked into P, contributing to P’s off-path summary. Each cluster C stores an aggregate Agg(C) and possibly a lazy tag Tag(C) so that Agg(Compress(A, B)) = F(Agg(A), Agg(B)) and Agg(Rake(P, S)) = G(Agg(P), Agg(S)), for problem-specific merge functions F and G that are typically associative and compatible with lazy tags. A query exposes a pair of boundary vertices (for a path query) or a single boundary vertex plus a root (for a rooted subtree query) by promoting a top decomposition in which a logarithmic number of rakes and compresses reconstructs the relevant cluster. The amortized cost per update/query is O(log n), with constants depending on the balancing scheme; splay-based realizations use the standard potential-function analysis. Many practical implementations use a splay-based auxiliary tree per preferred path. Virtual aggregates encode the effect of raked subtrees at boundary vertices, allowing subtree queries in O(log n) and path operations with lazy propagation.

04When to Use

Use a top tree when you need to maintain a dynamic forest under frequent link/cut operations together with rich queries on paths and subtrees:

Path aggregates/updates under dynamic connectivity, e.g., sum/min/max/xor along u–v, or adding a value to all nodes/edges on u–v.
Rooted subtree aggregates when the root can change (by rerooting) or when the forest changes structure, e.g., maintaining the size/sum of a node’s subtree while edges are added or removed elsewhere.
Advanced algorithms such as dynamic minimum spanning forest maintenance, dynamic centroid/diameter maintenance, or heavy use in offline/online tree problems where both path and subtree information interact.
Situations where Link–Cut Trees are almost enough, but you also need subtree queries without awkward hacks, or you need to merge non-commutative information that is cleaner to express via explicit rake/compress clusters.

If your tree is static, a heavy-light decomposition or Euler tour might be simpler and faster. If you need only path queries/updates without subtree interaction, Link–Cut Trees already suffice. Choose top trees when both path and subtree operations must coexist under fully dynamic updates, especially in 2400–2800-level competitive problems.

⚠️Common Mistakes

Mixing on-path and off-path aggregates: Path queries must not include raked (off-path) data; subtree queries must include it. Keep two views: preferred-path aggregate and virtual (raked) aggregate.
Forgetting to adjust virtual aggregates during access: When you detach/attach the right child during access, you must add/subtract its cluster value from the node’s virtual sum; otherwise subtree queries become incorrect.
Incorrect lazy propagation: Path-lazy tags apply only to the preferred-path splay subtree; do not accidentally apply them to virtual aggregates. Subtree updates, if supported, require separate virtual tags and sizes.
Assuming commutativity unnecessarily: Top trees naturally handle oriented merges; do not reorder child clusters unless your merge function is commutative or you’ve accounted for direction.
Rerooting confusion: Subtree queries are defined with respect to a chosen root. Always make_root(root) (or maintain a consistent root) before subtree queries.
Cutting a non-edge or linking already-connected nodes: Always check connectivity (or use a contract that inputs are valid) to avoid corrupting the structure.
Skipping pushdowns before rotations: Splay code must push tags down along the access path before rotations; stale tags lead to incorrect sums and broken invariants.

Key Formulas

Top-Tree Operation Time

O (lo g n)

Explanation: Each link, cut, access, and query/update touches a logarithmic number of clusters due to balanced restructuring with splay rotations. The bound is amortized over a sequence of operations.

Splay Potential Function

Φ = x \in aux \sum lo g (size (x))

Explanation: Amortized analysis uses a potential equal to the sum of logarithms of subtree sizes in the auxiliary trees. Rotations reduce potential enough to pay for rebalancing steps, yielding O(log n) amortized time.

Compress Merge

Agg (Compress (A, B)) = F (Agg (A), Agg (B))

Explanation: The aggregate stored for a compressed path cluster is the merge of child aggregates via a problem-specific associative function F that respects orientation when needed.

Rake Merge

Agg (Rake (P, S)) = G (Agg (P), Agg (S))

Explanation: Raking attaches a subtree to a path cluster and updates the path’s aggregate using a function G that adds the off-path contribution into a separate virtual summary.

Preferred-Path Aggregate

pathSum (v) = val (v) + pathSum (left (v)) + pathSum (right (v))

Explanation: In the auxiliary splay, the path aggregate is just the sum over the splay subtree. This excludes off-path (virtual) contributions, which are not children in the splay.

Rooted Subtree via Access

subtreeSum (v) = pathSum (v) - pathSum (right (v)) + virSum (v)

Explanation: After access(v) and splay(v), the right child is the path toward the root; removing it and adding virtual (raked) sums yields the sum of v’s rooted subtree.

Arithmetic Series (for testing)

i = 1 \sum n i = \frac{n ( n + 1 )}{2}

Explanation: Useful for verifying path or subtree sums in tests; it states the sum of the first n integers equals n(n+1)/2.

Logarithmic Recurrence

T (n) = T (n /2) + O (1) \Rightarrow T (n) = O (lo g n)

Explanation: Many top-tree operations halve ‘distance to root’ potential through rotations repeatedly, giving logarithmic amortized complexity.

Complexity Analysis

Top trees implemented with splay-based auxiliary trees achieve O(log n) amortized time per operation. The key step in most operations is access (expose), which walks up the represented tree, repeatedly splaying a node and changing its right child. Each splay operation performs O(1) rotations on average, and the amortized cost of a splay is O(log n) under the classic potential function Φ = Σ log(size(x)) across the auxiliary (preferred-path) trees. Therefore, access, mak

e_{r} oo t

, link, cut, and path queries/updates each cost O(log n) amortized. Path updates with lazy propagation set a tag at an exposed splay root and affect only O(log n) nodes during subsequent pushes/rotations, so they remain O(log n) amortized. Subtree queries (with respect to a designated root) are performed by access(v); splay(v); then combining the splay aggregate on v excluding its right child plus the virtual (raked) sum at v. Updating the virtual sum correctly during access ensures that subtree queries also run in O(log n). Space complexity is O(n), storing one auxiliary node per original vertex (or per edge in an edge-based variant), plus a constant number of fields: pointers/indices, lazy flags, and aggregates (both on-path and virtual). If you also store sizes for lazy scaling, edge weights, or multiple aggregates (sum/min/max), the overhead is still linear. Constants are modest in practice but higher than static decompositions. The amortized bound assumes reasonably random or adversarial sequences; pathological sequences are still bounded by the potential method of splay trees.

Code Examples

Top Tree (splay-based) for link/cut and path sum query

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct TopTree {
5     struct Node {
6         int ch[2]{0,0}, p{0};
7         bool rev{false};                // lazy reverse tag (for make_root)
8         long long val{0};               // node value
9         long long pathSum{0};           // sum over preferred-path (splay) subtree
10         long long add{0};               // lazy add for path updates (on splay only)
11         long long virSum{0};            // sum of all raked (virtual) subtrees attached here
12         int sz{1};                      // size of splay subtree (for scaling lazy add)
13     };
14 
15     int n; 
16     vector<Node> t;
17 
18     TopTree(int n=0): n(n), t(n+1) {}
19 
20     bool isRoot(int x){
21         int p=t[x].p; 
22         return p==0 || (t[p].ch[0]!=x && t[p].ch[1]!=x);
23     }
24     int dir(int x){ return t[t[x].p].ch[1]==x; }
25 
26     void apply_rev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev ^= 1; }
27     void apply_add(int x, long long d){ if(!x) return; t[x].val += d; t[x].pathSum += d * t[x].sz; t[x].add += d; }
28 
29     void push_up(int x){
30         t[x].sz = 1; t[x].pathSum = t[x].val;
31         if(t[x].ch[0]){ t[x].sz += t[t[x].ch[0]].sz; t[x].pathSum += t[t[x].ch[0]].pathSum; }
32         if(t[x].ch[1]){ t[x].sz += t[t[x].ch[1]].sz; t[x].pathSum += t[t[x].ch[1]].pathSum; }
33     }
34 
35     void push_down(int x){
36         if(t[x].rev){ apply_rev(t[x].ch[0]); apply_rev(t[x].ch[1]); t[x].rev=false; }
37         if(t[x].add){ apply_add(t[x].ch[0], t[x].add); apply_add(t[x].ch[1], t[x].add); t[x].add=0; }
38     }
39 
40     void rotate(int x){
41         int p=t[x].p, g=t[p].p, d=dir(x), b=t[x].ch[d^1];
42         if(!isRoot(p)) t[g].ch[dir(p)] = x; t[x].p = g;
43         t[x].ch[d^1] = p; t[p].p = x;
44         t[p].ch[d] = b; if(b) t[b].p = p;
45         push_up(p); push_up(x);
46     }
47 
48     void push_all(int x){
49         static vector<int> st; st.clear();
50         int y=x; st.push_back(y);
51         while(!isRoot(y)){ y=t[y].p; st.push_back(y);} 
52         while(!st.empty()){ push_down(st.back()); st.pop_back(); }
53     }
54 
55     void splay(int x){
56         push_all(x);
57         while(!isRoot(x)){
58             int p=t[x].p; if(!isRoot(p)) rotate(dir(x)==dir(p)? p : x); rotate(x);
59         }
60         push_up(x);
61     }
62 
63     // access: expose path to root; maintain virtual sums
64     void access(int x){
65         int last = 0;
66         for(int u=x; u; u=t[u].p){
67             splay(u);
68             // detach right child -> becomes virtual
69             int r = t[u].ch[1];
70             if(r){ t[u].ch[1]=0; t[r].p=0; t[u].virSum += t[r].pathSum; push_up(u); }
71             // attach previous preferred path as right child
72             if(last){ t[u].ch[1]=last; t[last].p=u; t[u].virSum -= t[last].pathSum; push_up(u); }
73             last = u;
74         }
75         splay(x);
76     }
77 
78     void make_root(int x){ access(x); apply_rev(x); }
79 
80     int find_root(int x){
81         access(x); 
82         // go to the leftmost node
83         int u=x; push_down(u);
84         while(t[u].ch[0]){ u=t[u].ch[0]; push_down(u);} 
85         splay(u); return u;
86     }
87 
88     bool connected(int u, int v){ return find_root(u)==find_root(v); }
89 
90     // Link u-v (assumes not connected). Also update virSum at v to include the new virtual child.
91     void link(int u, int v){
92         make_root(u);
93         if(find_root(v)==u) return; // already connected (or invalid)
94         access(v); // v becomes top
95         t[u].p = v;
96         t[v].virSum += t[u].pathSum; // u is attached off the preferred path of v
97         push_up(v);
98     }
99 
100     // Cut edge u-v (assumes it exists).
101     void cut(int u, int v){
102         make_root(u); access(v); // now u-v path is preferred; u should be left child of v
103         // detach u from v if directly connected
104         if(t[v].ch[0]==u && t[u].ch[1]==0){
105             t[v].ch[0]=0; t[u].p=0; push_up(v); // u completely separated; no virSum change (was preferred)
106         }
107     }
108 
109     // Path add: add d to all nodes on path u-v
110     void path_add(int u, int v, long long d){ make_root(u); access(v); apply_add(v,d); }
111 
112     // Path sum: sum of values on path u-v
113     long long path_sum(int u, int v){ make_root(u); access(v); return t[v].pathSum; }
114 
115     // Subtree sum of v with respect to chosen root r
116     long long subtree_sum(int v, int r){
117         make_root(r); access(v); // right child is path from v up to r
118         long long rightSum = t[v].ch[1]? t[t[v].ch[1]].pathSum : 0LL;
119         return (t[v].pathSum - rightSum) + t[v].virSum; // val+left+virtual
120     }
121 
122     void set_value(int x, long long newVal){ access(x); // splay at x
123         // update node to new value (preserve lazy correctness)
124         long long delta = newVal - t[x].val;
125         apply_add(x, delta);
126     }
127 };
128 
129 int main(){
130     ios::sync_with_stdio(false); cin.tie(nullptr);
131     int n=5; TopTree tt(n);
132     // Initialize node values 1..5
133     for(int i=1;i<=n;i++) tt.set_value(i, i);
134 
135     // Build a chain: 1-2-3-4-5
136     tt.link(1,2); tt.link(2,3); tt.link(3,4); tt.link(4,5);
137 
138     cout << tt.path_sum(1,5) << "\n";      // 1+2+3+4+5 = 15
139     tt.path_add(2,4, 10);                  // add 10 to nodes 2..4 on the path 2-4
140     cout << tt.path_sum(1,5) << "\n";      // 1+(2+10)+(3+10)+(4+10)+5 = 45
141 
142     // Subtree sum with root=1: subtree(3) = nodes {3,4,5}
143     cout << tt.subtree_sum(3, 1) << "\n";  // (3+10)+(4+10)+5 = 32
144 
145     // Cut 3-4 and query again
146     tt.cut(3,4);
147     cout << tt.connected(1,5) << "\n";    // 0 (false)
148     cout << tt.path_sum(1,3) << "\n";      // 1+(2+10)+(3+10) = 26
149 }
150

This splay-based top tree exposes preferred paths (access) and keeps off-path (raked) contributions in virSum. It supports link/cut, path add, path sum, and rooted subtree sum in O(log n) amortized time. Path updates affect only the preferred-path splay; virtual sums remain intact, matching the top-tree rake/compact intuition.

Time: O(log n) amortized per operationSpace: O(n)

Top Tree template for custom path aggregate (min) without updates

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 struct TopTreeMin {
5     struct Node{
6         int ch[2]{0,0}, p{0}; bool rev{false};
7         long long val{(long long)4e18}; // node weight
8         long long pathMin{(long long)4e18}; // min over splay subtree (preferred-path)
9         long long virMin{(long long)4e18};  // min of raked subtrees at this node
10     };
11     int n; vector<Node> t;
12     TopTreeMin(int n=0): n(n), t(n+1) {}
13 
14     bool isRoot(int x){ int p=t[x].p; return p==0 || (t[p].ch[0]!=x && t[p].ch[1]!=x);} 
15     int dir(int x){ return t[t[x].p].ch[1]==x; }
16     void apply_rev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev^=1; }
17     void push_down(int x){ if(t[x].rev){ apply_rev(t[x].ch[0]); apply_rev(t[x].ch[1]); t[x].rev=false; } }
18 
19     long long getMin(int x){ return x? t[x].pathMin : (long long)4e18; }
20 
21     void push_up(int x){
22         t[x].pathMin = min({ t[x].val, getMin(t[x].ch[0]), getMin(t[x].ch[1]) });
23     }
24 
25     void rotate(int x){
26         int p=t[x].p, g=t[p].p, d=dir(x), b=t[x].ch[d^1];
27         if(!isRoot(p)) t[g].ch[dir(p)] = x; t[x].p=g;
28         t[x].ch[d^1]=p; t[p].p=x;
29         t[p].ch[d]=b; if(b) t[b].p=p;
30         push_up(p); push_up(x);
31     }
32 
33     void push_all(int x){ vector<int> st; int y=x; st.push_back(y); while(!isRoot(y)){ y=t[y].p; st.push_back(y);} while(!st.empty()){ push_down(st.back()); st.pop_back(); } }
34     void splay(int x){ push_all(x); while(!isRoot(x)){ int p=t[x].p; if(!isRoot(p)) rotate(dir(x)==dir(p)?p:x); rotate(x);} push_up(x);} 
35 
36     void access(int x){ int last=0; for(int u=x;u;u=t[u].p){ splay(u); int r=t[u].ch[1]; if(r){ t[u].ch[1]=0; t[r].p=0; t[u].virMin=min(t[u].virMin, t[r].pathMin); push_up(u);} if(last){ t[u].ch[1]=last; t[last].p=u; /* remove from virMin not needed since we take min – keep careful if you track precise partition */ push_up(u);} last=u;} splay(x);} 
37 
38     void make_root(int x){ access(x); apply_rev(x);} 
39 
40     int find_root(int x){ access(x); int u=x; while(t[u].ch[0]){ push_down(u); u=t[u].ch[0]; } splay(u); return u; }
41 
42     void link(int u, int v){ make_root(u); if(find_root(v)==u) return; t[u].p=v; }
43     void cut(int u, int v){ make_root(u); access(v); if(t[v].ch[0]==u && t[u].ch[1]==0){ t[v].ch[0]=0; t[u].p=0; push_up(v);} }
44 
45     void set_value(int x, long long w){ access(x); t[x].val=w; push_up(x);} 
46 
47     long long path_min(int u, int v){ make_root(u); access(v); return t[v].pathMin; }
48 };
49 
50 int main(){
51     ios::sync_with_stdio(false); cin.tie(nullptr);
52     int n=4; TopTreeMin tt(n);
53     tt.set_value(1, 5); tt.set_value(2, 2); tt.set_value(3, 7); tt.set_value(4, 1);
54     tt.link(1,2); tt.link(2,3); tt.link(3,4);
55     cout << tt.path_min(1,4) << "\n"; // min on path 1-4: min{5,2,7,1} = 1
56     tt.cut(3,4);
57     cout << tt.path_min(1,3) << "\n"; // min on path 1-3: min{5,2,7} = 2
58 }
59

This variant shows how to change the aggregate to a different operator (min instead of sum). It omits lazy updates and keeps the same O(log n) structure for link/cut and path queries. For non-sum functions, be careful with virtual bookkeeping—here we demonstrate only path aggregates.

Time: O(log n) amortized per link/cut/querySpace: O(n)

Demonstration: dynamic forest with path add/sum and rooted subtree sum queries

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 // Reuse the TopTree from Example 1 (copy the implementation here in practice).
5 struct TopTree {
6     struct Node{ int ch[2]{0,0}, p{0}; bool rev{false}; long long val{0}, pathSum{0}, add{0}, virSum{0}; int sz{1}; };
7     int n; vector<Node> t; TopTree(int n=0):n(n),t(n+1){}
8     bool isRoot(int x){ int p=t[x].p; return p==0 || (t[p].ch[0]!=x && t[p].ch[1]!=x);} int dir(int x){ return t[t[x].p].ch[1]==x; }
9     void apply_rev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev^=1; }
10     void apply_add(int x,long long d){ if(!x) return; t[x].val+=d; t[x].pathSum+=d*t[x].sz; t[x].add+=d; }
11     void push_up(int x){ t[x].sz=1; t[x].pathSum=t[x].val; if(t[x].ch[0]){ t[x].sz+=t[t[x].ch[0]].sz; t[x].pathSum+=t[t[x].ch[0]].pathSum;} if(t[x].ch[1]){ t[x].sz+=t[t[x].ch[1]].sz; t[x].pathSum+=t[t[x].ch[1]].pathSum;} }
12     void push_down(int x){ if(t[x].rev){ apply_rev(t[x].ch[0]); apply_rev(t[x].ch[1]); t[x].rev=false;} if(t[x].add){ apply_add(t[x].ch[0], t[x].add); apply_add(t[x].ch[1], t[x].add); t[x].add=0; } }
13     void rotate(int x){ int p=t[x].p,g=t[p].p,d=dir(x),b=t[x].ch[d^1]; if(!isRoot(p)) t[g].ch[dir(p)]=x; t[x].p=g; t[x].ch[d^1]=p; t[p].p=x; t[p].ch[d]=b; if(b) t[b].p=p; push_up(p); push_up(x);} 
14     void push_all(int x){ vector<int> st; int y=x; st.push_back(y); while(!isRoot(y)){ y=t[y].p; st.push_back(y);} while(!st.empty()){ push_down(st.back()); st.pop_back(); } }
15     void splay(int x){ push_all(x); while(!isRoot(x)){ int p=t[x].p; if(!isRoot(p)) rotate(dir(x)==dir(p)?p:x); rotate(x);} push_up(x);} 
16     void access(int x){ int last=0; for(int u=x;u;u=t[u].p){ splay(u); int r=t[u].ch[1]; if(r){ t[u].ch[1]=0; t[r].p=0; t[u].virSum += t[r].pathSum; push_up(u);} if(last){ t[u].ch[1]=last; t[last].p=u; t[u].virSum -= t[last].pathSum; push_up(u);} last=u;} splay(x);} 
17     void make_root(int x){ access(x); apply_rev(x);} 
18     int find_root(int x){ access(x); int u=x; while(t[u].ch[0]){ push_down(u); u=t[u].ch[0]; } splay(u); return u; }
19     bool connected(int u,int v){ return find_root(u)==find_root(v);} 
20     void link(int u,int v){ make_root(u); if(find_root(v)==u) return; access(v); t[u].p=v; t[v].virSum += t[u].pathSum; push_up(v);} 
21     void cut(int u,int v){ make_root(u); access(v); if(t[v].ch[0]==u && t[u].ch[1]==0){ t[v].ch[0]=0; t[u].p=0; push_up(v);} }
22     void path_add(int u,int v,long long d){ make_root(u); access(v); apply_add(v,d);} 
23     long long path_sum(int u,int v){ make_root(u); access(v); return t[v].pathSum; } 
24     long long subtree_sum(int v,int r){ make_root(r); access(v); long long rightSum = t[v].ch[1]? t[t[v].ch[1]].pathSum:0; return (t[v].pathSum - rightSum) + t[v].virSum; } 
25     void set_value(int x,long long nv){ access(x); long long d=nv - t[x].val; apply_add(x,d);} 
26 };
27 
28 int main(){
29     ios::sync_with_stdio(false); cin.tie(nullptr);
30     int n,q; cin>>n>>q;
31     TopTree tt(n);
32     for(int i=1;i<=n;i++){ long long w; cin>>w; tt.set_value(i,w);} 
33 
34     // Initially a forest; operations:
35     // 1 u v : link u v
36     // 2 u v : cut u v
37     // 3 u v : path sum u v
38     // 4 u v d : path add d on u v
39     // 5 r v : subtree sum of v with respect to root r
40 
41     while(q--){
42         int tpy; cin>>tpy;
43         if(tpy==1){int u,v;cin>>u>>v; tt.link(u,v);} 
44         else if(tpy==2){int u,v;cin>>u>>v; tt.cut(u,v);} 
45         else if(tpy==3){int u,v;cin>>u>>v; cout<<tt.path_sum(u,v)<<"\n";} 
46         else if(tpy==4){int u,v; long long d;cin>>u>>v>>d; tt.path_add(u,v,d);} 
47         else if(tpy==5){int r,v;cin>>r>>v; cout<<tt.subtree_sum(v,r)<<"\n";} 
48     }
49 }
50

A small driver that uses the top-tree API to manage a dynamic forest. It shows how to interleave link/cut with path add/sum and rooted subtree sum queries. The subtree query requires specifying the current root r.

Time: Each operation runs in O(log n) amortized timeSpace: O(n)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct TopTree {
5	struct Node {
6	int ch[2]{0,0}, p{0};
7	bool rev{false}; // lazy reverse tag (for make_root)
8	long long val{0}; // node value
9	long long pathSum{0}; // sum over preferred-path (splay) subtree
10	long long add{0}; // lazy add for path updates (on splay only)
11	long long virSum{0}; // sum of all raked (virtual) subtrees attached here
12	int sz{1}; // size of splay subtree (for scaling lazy add)
13	};
14
15	int n;
16	vector<Node> t;
17
18	TopTree(int n=0): n(n), t(n+1) {}
19
20	bool isRoot(int x){
21	int p=t[x].p;
22	return p==0 \|\| (t[p].ch[0]!=x && t[p].ch[1]!=x);
23	}
24	int dir(int x){ return t[t[x].p].ch[1]==x; }
25
26	void apply_rev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev ^= 1; }
27	void apply_add(int x, long long d){ if(!x) return; t[x].val += d; t[x].pathSum += d * t[x].sz; t[x].add += d; }
28
29	void push_up(int x){
30	t[x].sz = 1; t[x].pathSum = t[x].val;
31	if(t[x].ch[0]){ t[x].sz += t[t[x].ch[0]].sz; t[x].pathSum += t[t[x].ch[0]].pathSum; }
32	if(t[x].ch[1]){ t[x].sz += t[t[x].ch[1]].sz; t[x].pathSum += t[t[x].ch[1]].pathSum; }
33	}
34
35	void push_down(int x){
36	if(t[x].rev){ apply_rev(t[x].ch[0]); apply_rev(t[x].ch[1]); t[x].rev=false; }
37	if(t[x].add){ apply_add(t[x].ch[0], t[x].add); apply_add(t[x].ch[1], t[x].add); t[x].add=0; }
38	}
39
40	void rotate(int x){
41	int p=t[x].p, g=t[p].p, d=dir(x), b=t[x].ch[d^1];
42	if(!isRoot(p)) t[g].ch[dir(p)] = x; t[x].p = g;
43	t[x].ch[d^1] = p; t[p].p = x;
44	t[p].ch[d] = b; if(b) t[b].p = p;
45	push_up(p); push_up(x);
46	}
47
48	void push_all(int x){
49	static vector<int> st; st.clear();
50	int y=x; st.push_back(y);
51	while(!isRoot(y)){ y=t[y].p; st.push_back(y);}
52	while(!st.empty()){ push_down(st.back()); st.pop_back(); }
53	}
54
55	void splay(int x){
56	push_all(x);
57	while(!isRoot(x)){
58	int p=t[x].p; if(!isRoot(p)) rotate(dir(x)==dir(p)? p : x); rotate(x);
59	}
60	push_up(x);
61	}
62
63	// access: expose path to root; maintain virtual sums
64	void access(int x){
65	int last = 0;
66	for(int u=x; u; u=t[u].p){
67	splay(u);
68	// detach right child -> becomes virtual
69	int r = t[u].ch[1];
70	if(r){ t[u].ch[1]=0; t[r].p=0; t[u].virSum += t[r].pathSum; push_up(u); }
71	// attach previous preferred path as right child
72	if(last){ t[u].ch[1]=last; t[last].p=u; t[u].virSum -= t[last].pathSum; push_up(u); }
73	last = u;
74	}
75	splay(x);
76	}
77
78	void make_root(int x){ access(x); apply_rev(x); }
79
80	int find_root(int x){
81	access(x);
82	// go to the leftmost node
83	int u=x; push_down(u);
84	while(t[u].ch[0]){ u=t[u].ch[0]; push_down(u);}
85	splay(u); return u;
86	}
87
88	bool connected(int u, int v){ return find_root(u)==find_root(v); }
89
90	// Link u-v (assumes not connected). Also update virSum at v to include the new virtual child.
91	void link(int u, int v){
92	make_root(u);
93	if(find_root(v)==u) return; // already connected (or invalid)
94	access(v); // v becomes top
95	t[u].p = v;
96	t[v].virSum += t[u].pathSum; // u is attached off the preferred path of v
97	push_up(v);
98	}
99
100	// Cut edge u-v (assumes it exists).
101	void cut(int u, int v){
102	make_root(u); access(v); // now u-v path is preferred; u should be left child of v
103	// detach u from v if directly connected
104	if(t[v].ch[0]==u && t[u].ch[1]==0){
105	t[v].ch[0]=0; t[u].p=0; push_up(v); // u completely separated; no virSum change (was preferred)
106	}
107	}
108
109	// Path add: add d to all nodes on path u-v
110	void path_add(int u, int v, long long d){ make_root(u); access(v); apply_add(v,d); }
111
112	// Path sum: sum of values on path u-v
113	long long path_sum(int u, int v){ make_root(u); access(v); return t[v].pathSum; }
114
115	// Subtree sum of v with respect to chosen root r
116	long long subtree_sum(int v, int r){
117	make_root(r); access(v); // right child is path from v up to r
118	long long rightSum = t[v].ch[1]? t[t[v].ch[1]].pathSum : 0LL;
119	return (t[v].pathSum - rightSum) + t[v].virSum; // val+left+virtual
120	}
121
122	void set_value(int x, long long newVal){ access(x); // splay at x
123	// update node to new value (preserve lazy correctness)
124	long long delta = newVal - t[x].val;
125	apply_add(x, delta);
126	}
127	};
128
129	int main(){
130	ios::sync_with_stdio(false); cin.tie(nullptr);
131	int n=5; TopTree tt(n);
132	// Initialize node values 1..5
133	for(int i=1;i<=n;i++) tt.set_value(i, i);
134
135	// Build a chain: 1-2-3-4-5
136	tt.link(1,2); tt.link(2,3); tt.link(3,4); tt.link(4,5);
137
138	cout << tt.path_sum(1,5) << "\n"; // 1+2+3+4+5 = 15
139	tt.path_add(2,4, 10); // add 10 to nodes 2..4 on the path 2-4
140	cout << tt.path_sum(1,5) << "\n"; // 1+(2+10)+(3+10)+(4+10)+5 = 45
141
142	// Subtree sum with root=1: subtree(3) = nodes {3,4,5}
143	cout << tt.subtree_sum(3, 1) << "\n"; // (3+10)+(4+10)+5 = 32
144
145	// Cut 3-4 and query again
146	tt.cut(3,4);
147	cout << tt.connected(1,5) << "\n"; // 0 (false)
148	cout << tt.path_sum(1,3) << "\n"; // 1+(2+10)+(3+10) = 26
149	}
150

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	struct TopTreeMin {
5	struct Node{
6	int ch[2]{0,0}, p{0}; bool rev{false};
7	long long val{(long long)4e18}; // node weight
8	long long pathMin{(long long)4e18}; // min over splay subtree (preferred-path)
9	long long virMin{(long long)4e18}; // min of raked subtrees at this node
10	};
11	int n; vector<Node> t;
12	TopTreeMin(int n=0): n(n), t(n+1) {}
13
14	bool isRoot(int x){ int p=t[x].p; return p==0 \|\| (t[p].ch[0]!=x && t[p].ch[1]!=x);}
15	int dir(int x){ return t[t[x].p].ch[1]==x; }
16	void apply_rev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev^=1; }
17	void push_down(int x){ if(t[x].rev){ apply_rev(t[x].ch[0]); apply_rev(t[x].ch[1]); t[x].rev=false; } }
18
19	long long getMin(int x){ return x? t[x].pathMin : (long long)4e18; }
20
21	void push_up(int x){
22	t[x].pathMin = min({ t[x].val, getMin(t[x].ch[0]), getMin(t[x].ch[1]) });
23	}
24
25	void rotate(int x){
26	int p=t[x].p, g=t[p].p, d=dir(x), b=t[x].ch[d^1];
27	if(!isRoot(p)) t[g].ch[dir(p)] = x; t[x].p=g;
28	t[x].ch[d^1]=p; t[p].p=x;
29	t[p].ch[d]=b; if(b) t[b].p=p;
30	push_up(p); push_up(x);
31	}
32
33	void push_all(int x){ vector<int> st; int y=x; st.push_back(y); while(!isRoot(y)){ y=t[y].p; st.push_back(y);} while(!st.empty()){ push_down(st.back()); st.pop_back(); } }
34	void splay(int x){ push_all(x); while(!isRoot(x)){ int p=t[x].p; if(!isRoot(p)) rotate(dir(x)==dir(p)?p:x); rotate(x);} push_up(x);}
35
36	void access(int x){ int last=0; for(int u=x;u;u=t[u].p){ splay(u); int r=t[u].ch[1]; if(r){ t[u].ch[1]=0; t[r].p=0; t[u].virMin=min(t[u].virMin, t[r].pathMin); push_up(u);} if(last){ t[u].ch[1]=last; t[last].p=u; /* remove from virMin not needed since we take min – keep careful if you track precise partition */ push_up(u);} last=u;} splay(x);}
37
38	void make_root(int x){ access(x); apply_rev(x);}
39
40	int find_root(int x){ access(x); int u=x; while(t[u].ch[0]){ push_down(u); u=t[u].ch[0]; } splay(u); return u; }
41
42	void link(int u, int v){ make_root(u); if(find_root(v)==u) return; t[u].p=v; }
43	void cut(int u, int v){ make_root(u); access(v); if(t[v].ch[0]==u && t[u].ch[1]==0){ t[v].ch[0]=0; t[u].p=0; push_up(v);} }
44
45	void set_value(int x, long long w){ access(x); t[x].val=w; push_up(x);}
46
47	long long path_min(int u, int v){ make_root(u); access(v); return t[v].pathMin; }
48	};
49
50	int main(){
51	ios::sync_with_stdio(false); cin.tie(nullptr);
52	int n=4; TopTreeMin tt(n);
53	tt.set_value(1, 5); tt.set_value(2, 2); tt.set_value(3, 7); tt.set_value(4, 1);
54	tt.link(1,2); tt.link(2,3); tt.link(3,4);
55	cout << tt.path_min(1,4) << "\n"; // min on path 1-4: min{5,2,7,1} = 1
56	tt.cut(3,4);
57	cout << tt.path_min(1,3) << "\n"; // min on path 1-3: min{5,2,7} = 2
58	}
59

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	// Reuse the TopTree from Example 1 (copy the implementation here in practice).
5	struct TopTree {
6	struct Node{ int ch[2]{0,0}, p{0}; bool rev{false}; long long val{0}, pathSum{0}, add{0}, virSum{0}; int sz{1}; };
7	int n; vector<Node> t; TopTree(int n=0):n(n),t(n+1){}
8	bool isRoot(int x){ int p=t[x].p; return p==0 \|\| (t[p].ch[0]!=x && t[p].ch[1]!=x);} int dir(int x){ return t[t[x].p].ch[1]==x; }
9	void apply_rev(int x){ if(!x) return; swap(t[x].ch[0], t[x].ch[1]); t[x].rev^=1; }
10	void apply_add(int x,long long d){ if(!x) return; t[x].val+=d; t[x].pathSum+=d*t[x].sz; t[x].add+=d; }
11	void push_up(int x){ t[x].sz=1; t[x].pathSum=t[x].val; if(t[x].ch[0]){ t[x].sz+=t[t[x].ch[0]].sz; t[x].pathSum+=t[t[x].ch[0]].pathSum;} if(t[x].ch[1]){ t[x].sz+=t[t[x].ch[1]].sz; t[x].pathSum+=t[t[x].ch[1]].pathSum;} }
12	void push_down(int x){ if(t[x].rev){ apply_rev(t[x].ch[0]); apply_rev(t[x].ch[1]); t[x].rev=false;} if(t[x].add){ apply_add(t[x].ch[0], t[x].add); apply_add(t[x].ch[1], t[x].add); t[x].add=0; } }
13	void rotate(int x){ int p=t[x].p,g=t[p].p,d=dir(x),b=t[x].ch[d^1]; if(!isRoot(p)) t[g].ch[dir(p)]=x; t[x].p=g; t[x].ch[d^1]=p; t[p].p=x; t[p].ch[d]=b; if(b) t[b].p=p; push_up(p); push_up(x);}
14	void push_all(int x){ vector<int> st; int y=x; st.push_back(y); while(!isRoot(y)){ y=t[y].p; st.push_back(y);} while(!st.empty()){ push_down(st.back()); st.pop_back(); } }
15	void splay(int x){ push_all(x); while(!isRoot(x)){ int p=t[x].p; if(!isRoot(p)) rotate(dir(x)==dir(p)?p:x); rotate(x);} push_up(x);}
16	void access(int x){ int last=0; for(int u=x;u;u=t[u].p){ splay(u); int r=t[u].ch[1]; if(r){ t[u].ch[1]=0; t[r].p=0; t[u].virSum += t[r].pathSum; push_up(u);} if(last){ t[u].ch[1]=last; t[last].p=u; t[u].virSum -= t[last].pathSum; push_up(u);} last=u;} splay(x);}
17	void make_root(int x){ access(x); apply_rev(x);}
18	int find_root(int x){ access(x); int u=x; while(t[u].ch[0]){ push_down(u); u=t[u].ch[0]; } splay(u); return u; }
19	bool connected(int u,int v){ return find_root(u)==find_root(v);}
20	void link(int u,int v){ make_root(u); if(find_root(v)==u) return; access(v); t[u].p=v; t[v].virSum += t[u].pathSum; push_up(v);}
21	void cut(int u,int v){ make_root(u); access(v); if(t[v].ch[0]==u && t[u].ch[1]==0){ t[v].ch[0]=0; t[u].p=0; push_up(v);} }
22	void path_add(int u,int v,long long d){ make_root(u); access(v); apply_add(v,d);}
23	long long path_sum(int u,int v){ make_root(u); access(v); return t[v].pathSum; }
24	long long subtree_sum(int v,int r){ make_root(r); access(v); long long rightSum = t[v].ch[1]? t[t[v].ch[1]].pathSum:0; return (t[v].pathSum - rightSum) + t[v].virSum; }
25	void set_value(int x,long long nv){ access(x); long long d=nv - t[x].val; apply_add(x,d);}
26	};
27
28	int main(){
29	ios::sync_with_stdio(false); cin.tie(nullptr);
30	int n,q; cin>>n>>q;
31	TopTree tt(n);
32	for(int i=1;i<=n;i++){ long long w; cin>>w; tt.set_value(i,w);}
33
34	// Initially a forest; operations:
35	// 1 u v : link u v
36	// 2 u v : cut u v
37	// 3 u v : path sum u v
38	// 4 u v d : path add d on u v
39	// 5 r v : subtree sum of v with respect to root r
40
41	while(q--){
42	int tpy; cin>>tpy;
43	if(tpy==1){int u,v;cin>>u>>v; tt.link(u,v);}
44	else if(tpy==2){int u,v;cin>>u>>v; tt.cut(u,v);}
45	else if(tpy==3){int u,v;cin>>u>>v; cout<<tt.path_sum(u,v)<<"\n";}
46	else if(tpy==4){int u,v; long long d;cin>>u>>v>>d; tt.path_add(u,v,d);}
47	else if(tpy==5){int r,v;cin>>r>>v; cout<<tt.subtree_sum(v,r)<<"\n";}
48	}
49	}
50