Why this matters when you build with AI
Ask an AI tool for "path add and path sum on a tree" and you will often get code that looks like a segment tree with a tree bolted on. It fails in four common ways. It walks from both ends one step at a time, which is O(n) per query and times out with 200000 queries on a path. It compares the depths of the two current vertices instead of the depths of their chain heads, so it jumps over part of the path. It includes the top vertex of an edge query, which gives a sum that is off by one value. Or it uses a subtree range that is one position too long.
Each of these gives plausible answers on a small sample. You catch them by reading the loop, by writing a naive walk that is slow but obviously right, and by running both on random trees with random updates. This lesson builds one correct version and shows what each mistake looks like in output.
A prompt that states the operations and the limits:
Write C++17 code for a tree with up to 200000 vertices and 200000 operations.
Support: add x to every vertex on the path u..v; sum of vertex values on the path u..v;
add x to every vertex in the subtree of v. Use heavy-light decomposition with a
lazy segment tree. Do not use recursion on the tree. Say the cost of each operation.
Also say which vertex's value an edge query should not include.A good answer uses heavy-light decomposition, positions from a DFS that visits the heavy child first, and a lazy segment tree with long long sums. It states O(log^2 n) for path operations and O(log n) for subtree operations. Check each point by reading the code, then compare with a naive version (section "Check them against each other").
Terms used
- A rooted tree has a root at the top. Every other vertex has one parent. The depth of a vertex is the number of edges from the root to it.
- The size of a subtree is the number of vertices in it, including its root.
- The heavy child of a vertex is the child with the largest subtree. The other children are light children.
- A heavy chain is a path that goes down through heavy children only. Every vertex belongs to exactly one chain. The top vertex of a chain is its head.
- The position of a vertex is its index in an array. The positions are chosen so that each chain takes a contiguous block, and so that each subtree takes a contiguous block.
- A segment tree is a binary tree over an array. Each node stores the sum over its range, so a range sum or a range update costs O(log n).
- Lazy propagation is a way to apply a range update to a segment tree node without visiting its children. The node stores the pending update, and it is pushed down only when a child is needed.
- The lowest common ancestor (LCA) of u and v is the deepest vertex that is an ancestor of both. It is the top of the path from u to v.
The idea: long paths cross few light edges
Rooted at 0, the example tree from the tree DP lesson looks like this:
0 - 1 1 - 3 1 - 4
0 - 2 2 - 5 5 - 6Subtree sizes: vertex 0 has 7, vertex 1 has 3, vertex 2 has 3, vertex 5 has 2 and the leaves have 1. At vertex 0 the children 1 and 2 are tied at size 3, so the first one found is heavy. The heavy child of 1 is 3, and the heavy child of 5 is 6.
The chains are 0 - 1 - 3, then 4 on its own, then 2 - 5 - 6. The first chain starts at head 0. The second chain starts at head 4, which is a light child of 1. The third starts at head 2, which is the light child of 0.
The point of the decomposition is this claim: going from any vertex to the root, you cross at most log2 n light edges. Reason: take a vertex v and a light edge from p down to its child c. The subtree of p contains the subtree of c and at least as much again (its heavy child has at least as many vertices as c). So the subtree size at least doubles each time you cross a light edge going up. The size is at most n, so the number of light edges is at most log2 n. For n = 200000, that is 17, because 2^17 = 131072 and 2^18 = 262144.
So a path from u to v splits into at most about 2 * log2 n pieces, each piece being a run of one chain. Each piece is one contiguous range of positions, which the segment tree handles in O(log n). Total per path operation: O(log^2 n).
Positions: chains and subtrees as ranges
To make chains and subtrees contiguous, give positions from a DFS that visits the heavy child first. Then:
- the heavy child of v gets position
pos[v] + 1, so each chain is a block of consecutive positions, and - the subtree of v covers the positions
pos[v]topos[v] + size[v] - 1, because a DFS finishes the whole subtree before it leaves it.
The code uses a stack instead of recursion. It pushes the light children first and the heavy child last, so the heavy child is popped next. Running the code on the example gives this table (info.cpp, real output):
v parent depth size heavy head pos
0 -1 0 7 1 0 0
1 0 1 3 3 0 1
2 0 1 3 5 2 4
3 1 2 1 -1 0 2
4 1 2 1 -1 4 3
5 2 2 2 6 2 5
6 5 3 1 -1 2 6Read it like this: the subtree of 2 covers positions 4 to 6 (vertices 2, 5 and 6), which is three positions for a subtree of size 3. The chain 0 - 1 - 3 has positions 0, 1 and 2, which are consecutive.
Path query, step by step
To find the path sum from u to v, repeat these steps:
- If
head[u]andhead[v]are different, move the vertex whose head is deeper up to its chain's head. Add the range of positions from that head to the vertex, then jump to the parent of the head. - When both are on the same chain, the shallower one is the LCA. Add the range between the two positions and stop.
The rule in step 1 is "move the vertex whose chain head is deeper". Using the depth of the vertex itself breaks the proof that each jump leaves a chain.
Worked example: sum on the path from 3 to 6, with vertex values 1 to 7 (vertex v has value v + 1).
head[3] = 0andhead[6] = 2. The head of 6 is deeper (depth 1 against depth 0), so take 6 first. Its positions arepos[2]topos[6], which is 4 to 6. That covers vertices 2, 5 and 6, with values 3, 6 and 7. Sum 16. Jump toparent[2] = 0.- Now
head[0] = 0andhead[3] = 0, the same chain. The shallower vertex is 0. The positions arepos[0]topos[3], which is 0 to 2. That covers vertices 0, 1 and 3, with values 1, 2 and 4. Sum 7. - Total: 16 + 7 = 23.
Path update and subtree update
The update is the same loop, with add in place of sum. A subtree update is a single range update over [pos[v], pos[v] + size[v] - 1].
Vertex values and edge values
Vertex values and edge values differ in one detail. An edge (v, parent v) can be stored at the vertex v, because each non-root vertex has exactly one parent edge. So for a tree with n - 1 edges, store the edge value at the child and leave the root's slot unused.
An edge query from u to v needs the edges on the path, which are the edges from each path vertex up to its parent, except the one above the LCA. In the vertex version, the LCA's value is included. In the edge version it must be left out. The last range in the code starts at pos[u] + 1 for that reason.
Worked example, with edge values given by vals[v] = v + 1 stored at each child. The path 3 to 6 uses the edges 3-1, 1-0, 0-2, 2-5 and 5-6. Their stored values are the values of vertices 3, 1, 2, 5 and 6, which are 4, 2, 3, 6 and 7. Sum 22. Including the LCA would add the value of vertex 0, which is 1, and give 23. The program prints both (real output):
correct edge sum 3..6: 22
wrong (includes LCA) : 23
lca(3,6) = 0Complexity
- Build: O(n). The code makes a few linear passes over the tree and builds one segment tree.
- Path sum and path update: O(log^2 n). There are at most about 2 log n chain pieces and each piece costs O(log n).
- Subtree sum and subtree update: O(log n).
- Memory: O(n) for the tree and the segment tree (about 4n long long values for sums and the same for lazy tags).
Measured on this machine (WSL2, g++ 15.2.0 with -O2): 200000 random operations on a tree of 200000 vertices, built as parent(i) = i / 2, took 0.8 s wall time, including reading about 600000 numbers. This is one run on one machine, and it is only a sanity check, not a benchmark.
The C++17 code
The data structure is in hld.hpp. Its lazy segment tree is a separate class. The main program reads the tree, the initial values and a list of operations, and prints the answer to each sum query.
#pragma once
#include <algorithm>
#include <cstddef>
#include <memory>
#include <utility>
#include <vector>
// Lazy segment tree: range add, range sum, over positions 0 .. n-1.
class LazySum {
public:
explicit LazySum(const std::vector<long long>& init) : n_(static_cast<int>(init.size())) {
sum_.assign(4 * n_ + 4, 0);
lazy_.assign(4 * n_ + 4, 0);
if (n_ > 0) build(1, 0, n_ - 1, init);
}
void add(int l, int r, long long x) { add(1, 0, n_ - 1, l, r, x); }
long long query(int l, int r) { return query(1, 0, n_ - 1, l, r); }
private:
int n_;
std::vector<long long> sum_, lazy_; // lazy_[node]: pending add for each element below node
void build(int node, int lo, int hi, const std::vector<long long>& init) {
if (lo == hi) {
sum_[node] = init[lo];
return;
}
int mid = (lo + hi) / 2;
build(2 * node, lo, mid, init);
build(2 * node + 1, mid + 1, hi, init);
sum_[node] = sum_[2 * node] + sum_[2 * node + 1];
}
void apply(int node, int lo, int hi, long long x) {
sum_[node] += x * (hi - lo + 1);
lazy_[node] += x;
}
void push(int node, int lo, int hi) {
if (lazy_[node] == 0) return;
int mid = (lo + hi) / 2;
apply(2 * node, lo, mid, lazy_[node]);
apply(2 * node + 1, mid + 1, hi, lazy_[node]);
lazy_[node] = 0;
}
void add(int node, int lo, int hi, int l, int r, long long x) {
if (r < lo || hi < l) return;
if (l <= lo && hi <= r) {
apply(node, lo, hi, x);
return;
}
push(node, lo, hi);
int mid = (lo + hi) / 2;
add(2 * node, lo, mid, l, r, x);
add(2 * node + 1, mid + 1, hi, l, r, x);
sum_[node] = sum_[2 * node] + sum_[2 * node + 1];
}
long long query(int node, int lo, int hi, int l, int r) {
if (r < lo || hi < l) return 0;
if (l <= lo && hi <= r) return sum_[node];
push(node, lo, hi);
int mid = (lo + hi) / 2;
return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);
}
};
// Heavy-light decomposition of a tree with vertices 0 .. n-1, rooted at 0.
// vals[v] is the value of vertex v. For edge values, pass the value of the
// edge (v, parent(v)) as vals[v], and use the edge_* functions.
class HLD {
public:
HLD(int n, const std::vector<std::pair<int, int>>& edges, const std::vector<long long>& vals)
: n_(n), adj_(n), parent_(n, -1), depth_(n, 0), sz_(n, 1), heavy_(n, -1),
head_(n, -1), pos_(n, -1), at_(n, -1) {
for (auto [a, b] : edges) {
adj_[a].push_back(b);
adj_[b].push_back(a);
}
// Step 1: BFS order gives parent and depth without recursion.
std::vector<int> order;
order.reserve(n);
std::vector<char> seen(n, 0);
order.push_back(0);
seen[0] = 1;
for (std::size_t i = 0; i < order.size(); ++i) {
int v = order[i];
for (int w : adj_[v]) {
if (!seen[w]) {
seen[w] = 1;
parent_[w] = v;
depth_[w] = depth_[v] + 1;
order.push_back(w);
}
}
}
// Step 2: subtree sizes, from the leaves up.
for (int i = n - 1; i >= 1; --i) sz_[parent_[order[i]]] += sz_[order[i]];
// Step 3: heavy child = the child with the largest subtree.
for (int i = 1; i < n; ++i) {
int v = order[i];
int p = parent_[v];
if (heavy_[p] == -1 || sz_[v] > sz_[heavy_[p]]) heavy_[p] = v;
}
// Step 4: positions from a DFS that visits the heavy child first.
// Then a chain is contiguous, and so is every subtree.
std::vector<int> st{0};
int timer = 0;
while (!st.empty()) {
int v = st.back();
st.pop_back();
pos_[v] = timer;
at_[timer] = v;
++timer;
for (int w : adj_[v]) {
if (w != parent_[v] && w != heavy_[v]) st.push_back(w);
}
if (heavy_[v] != -1) st.push_back(heavy_[v]); // popped next
}
// Step 5: head of each chain (its top vertex). Parents come before children in pos order.
for (int t = 0; t < n; ++t) {
int v = at_[t];
if (parent_[v] == -1 || heavy_[parent_[v]] != v) head_[v] = v;
else head_[v] = head_[parent_[v]];
}
std::vector<long long> by_pos(n);
for (int v = 0; v < n; ++v) by_pos[pos_[v]] = vals[v];
seg_ = std::make_unique<LazySum>(by_pos);
}
// Add x to every vertex on the path from u to v (both ends included).
void path_add(int u, int v, long long x) {
while (head_[u] != head_[v]) {
if (depth_[head_[u]] < depth_[head_[v]]) std::swap(u, v);
seg_->add(pos_[head_[u]], pos_[u], x);
u = parent_[head_[u]];
}
if (depth_[u] > depth_[v]) std::swap(u, v);
seg_->add(pos_[u], pos_[v], x);
}
// Sum of vertex values on the path from u to v (both ends included).
long long path_sum(int u, int v) {
long long total = 0;
while (head_[u] != head_[v]) {
if (depth_[head_[u]] < depth_[head_[v]]) std::swap(u, v);
total += seg_->query(pos_[head_[u]], pos_[u]);
u = parent_[head_[u]];
}
if (depth_[u] > depth_[v]) std::swap(u, v);
return total + seg_->query(pos_[u], pos_[v]);
}
// Add x to every vertex in the subtree of v.
void subtree_add(int v, long long x) { seg_->add(pos_[v], pos_[v] + sz_[v] - 1, x); }
// Sum over the subtree of v.
long long subtree_sum(int v) { return seg_->query(pos_[v], pos_[v] + sz_[v] - 1); }
// Edge values: the edge (v, parent(v)) is stored at v. Sum over the edges
// on the path from u to v. The edge into the LCA is not on the path, so the
// last segment starts one position after the LCA.
long long edge_path_sum(int u, int v) {
long long total = 0;
while (head_[u] != head_[v]) {
if (depth_[head_[u]] < depth_[head_[v]]) std::swap(u, v);
total += seg_->query(pos_[head_[u]], pos_[u]); // includes head's edge up
u = parent_[head_[u]];
}
if (depth_[u] > depth_[v]) std::swap(u, v); // u is now the LCA
if (u == v) return total;
return total + seg_->query(pos_[u] + 1, pos_[v]);
}
int lca(int u, int v) const {
while (head_[u] != head_[v]) {
if (depth_[head_[u]] < depth_[head_[v]]) std::swap(u, v);
u = parent_[head_[u]];
}
return depth_[u] < depth_[v] ? u : v;
}
// Number of light edges (edges to a non-heavy child) from v up to the root.
int light_edges_to_root(int v) const {
int count = 0;
while (parent_[head_[v]] != -1) {
v = parent_[head_[v]];
++count;
}
return count;
}
int heavy(int v) const { return heavy_[v]; }
int head(int v) const { return head_[v]; }
int depth(int v) const { return depth_[v]; }
int parent(int v) const { return parent_[v]; }
int size_of(int v) const { return sz_[v]; }
int pos(int v) const { return pos_[v]; }
private:
int n_;
std::vector<std::vector<int>> adj_;
std::vector<int> parent_, depth_, sz_, heavy_, head_, pos_, at_;
std::unique_ptr<LazySum> seg_;
};#include <cstdio>
#include <utility>
#include <vector>
#include "hld.hpp"
// Input:
// line 1: n q
// line 2: n vertex values
// next n - 1 lines: "a b" for each edge
// next q lines, one of:
// 1 u v x add x to every vertex on the path u..v
// 2 u v print the sum of vertex values on the path u..v
// 3 v x add x to every vertex in the subtree of v
int main() {
int n, q;
if (std::scanf("%d %d", &n, &q) != 2) return 1;
std::vector<long long> vals(n);
for (int i = 0; i < n; ++i) {
if (std::scanf("%lld", &vals[i]) != 1) return 1;
}
std::vector<std::pair<int, int>> edges;
for (int i = 0; i + 1 < n; ++i) {
int a, b;
if (std::scanf("%d %d", &a, &b) != 2) return 1;
edges.emplace_back(a, b);
}
HLD h(n, edges, vals);
for (int i = 0; i < q; ++i) {
int type;
if (std::scanf("%d", &type) != 1) return 1;
if (type == 1) {
int u, v;
long long x;
if (std::scanf("%d %d %lld", &u, &v, &x) != 3) return 1;
h.path_add(u, v, x);
} else if (type == 2) {
int u, v;
if (std::scanf("%d %d", &u, &v) != 2) return 1;
std::printf("%lld\n", h.path_sum(u, v));
} else {
int v;
long long x;
if (std::scanf("%d %lld", &v, &x) != 2) return 1;
h.subtree_add(v, x);
}
}
return 0;
}Input for the example, saved as sample.txt. The values are 1 to 7, then the tree, then five operations:
7 5
1 2 3 4 5 6 7
0 1
0 2
1 3
1 4
2 5
5 6
2 3 6
1 3 6 10
2 3 6
3 1 2
2 6 6Real output of main on that input, compiled with g++ -O2 -std=c++17 -Wall -Wextra:
23
83
17Check the lines by hand. The first query is the sum on the path 3..6, which is 23 (worked above). The update adds 10 to the path 3, 1, 0, 2, 5, 6, which is six vertices, so the sum rises by 60 to 83. The subtree update adds 2 to the subtree of 1, which is vertices 1, 3 and 4. The last query reads vertex 6, which is 7 + 10 = 17. Vertex 6 is not in the subtree of 1, so the subtree update does not change it.
Check them against each other
The file stress.cpp builds random trees of up to 30 vertices, with random values, and runs 40 random operations on each one. It compares the HLD answers with a naive version that walks parent pointers one step at a time. The naive version is O(n) per operation and is obviously correct. The core of it:
// Naive reference: walk parent pointers, one step at a time.
void path_vertices(int u, int v, std::vector<int>& out) const {
while (u != v) {
if (depth[u] < depth[v]) std::swap(u, v);
out.push_back(u);
u = parent[u];
}
out.push_back(u);
}
void path_add(int u, int v, long long x) {
std::vector<int> vs;
path_vertices(u, v, vs);
for (int w : vs) val[w] += x;
}
void subtree_add(int v, long long x) {
for (int w = 0; w < n; ++w) {
int a = w;
while (a != -1 && a != v) a = parent[a];
if (a == v) val[w] += x;
}
}The stress test also checks that every vertex has at most log2 n light edges to the root. Real output with two seeds:
seed 7: 1500 trees, 120000 checks, all match; max light edges to root = 3
seed 99: 1500 trees, 120000 checks, all match; max light edges to root = 3Each "check" is one operation (path add, path sum, subtree add or subtree sum) or one edge query with its LCA. The largest number of light edges seen was 3, which is within the bound of log2 30, about 4.9.
Common mistakes
Mistake 1: comparing depths of the vertices, not their heads. Symptom: wrong sums on paths that cross a chain boundary. I replaced the head comparison with depth_[u] < depth_[v] in a copy and ran the stress test. It stopped at the first random path:
PATH SUM MISMATCH test 0 op 17: -811 vs -759Compare the depths of the heads, so that each jump moves up past a whole chain.
Mistake 2: the subtree range one position too long. Symptom: a subtree update changes one extra vertex, the one at position pos[v] + size[v]. I changed the end of the range to pos[v] + sz[v] in a copy and the stress test reported:
SUBTREE MISMATCH test 0 op 3: -1197 vs -1102The end of the range is pos[v] + size - 1, because both ends are included.
Mistake 3: including the LCA in an edge query. Symptom: the sum is one value too large, and the difference is exactly the value of the LCA. The example above gives 23 where 22 is correct. Use pos[u] + 1 as the start of the last range, where u is the shallower vertex.
Mistake 4: positions from a BFS order. Expected symptom (I did not run this one): subtree queries return sums over the wrong set of vertices, because a subtree is not one block of positions in BFS order. BFS lists the children of a vertex together, but not the whole subtree. Use the DFS from step 4.
Mistake 5: forgetting to push lazy tags. Expected symptom (I did not run this one): a range query misses an update that was made to a larger range earlier, so the answer is too small by that update's amount on the overlap. Every node that is split must be pushed before its children are read or changed.
Checklist
- Build the heavy child from subtree sizes, after a bottom-up pass.
- Assign positions with a DFS that visits the heavy child first, using a stack if you want no recursion.
- A chain is a block of consecutive positions. A subtree is a block of positions from
pos[v]topos[v] + size[v] - 1. - In the path loop, move the vertex whose head is deeper.
- For edge values, store each edge at its lower vertex, and leave out the LCA's position in the last range.
- Use
long longfor sums and for the lazy tags. - Compare with a naive walk on random trees, including paths and stars, with both vertex and edge queries.
What was checked
- All C++ code compiled with g++ 15.2.0 (Ubuntu 15.2.0-16ubuntu1) using
-O2 -std=c++17 -Wall -Wextra, with no warnings. - The stress test passed on 1500 random trees with seed 7 and 1500 with seed 99, against the naive walk, including the LCA check for edge queries.
- The sample output (23, 83, 17) was compared with a hand trace.
- The chain table (
info.cpp) was checked by hand against the example tree: the subtree of 2 covers positions 4 to 6, and the chain 0 - 1 - 3 covers positions 0 to 2. - Mistakes 1 to 3 were run, and the printed lines were copied from the output. Mistakes 1 and 2 used a copy of the header with one line changed. Mistakes 4 and 5 are described, not run.
- Problem 1's answer (24) and Problem 4's method (sum 523 on the example with x = 100) were run with this code.
- The big run took 0.8 s wall time on this machine. This is one run and depends on the machine.
- I did not write a Python version. A segment tree in Python has a high constant factor, so the code is shown in C++ only.
Summary
Heavy-light decomposition splits a tree into chains, so that any path crosses only a few of them. Positions from a heavy-first DFS make each chain and each subtree one range, and a lazy segment tree answers range queries on those ranges. A path query becomes a loop over chains, and each step is one range query. The two details that cause most wrong answers are the direction of the head comparison and the LCA, and both are caught by a naive walk on random trees.
Practice
Problem 1: trace a path by hand
Use the example tree from this lesson. Find the chain pieces used by the path from 4 to 6, giving each piece as a range of positions. Then compute the sum of vertex values on the path with values 1 to 7, and check it with main.
Show the answer
Hint: start with head[4] and head[6]. Four is its own chain. Six's head is 2.
Answer: the head of 4 is 4 (depth 2) and the head of 6 is 2 (depth 1). Vertex 4 is deeper in its chain's head, so move 4 first: range pos[4] to pos[4], which is 3 to 3, value 5. Jump to parent[4] = 1. Now head[1] = 0 and head[6] = 2. Head 2 is deeper, so move 6: range pos[2] to pos[6], which is 4 to 6, values 3, 6 and 7, sum 16. Jump to parent[2] = 0. Now both are on chain 0. Range from pos[0] to pos[1], which is 0 to 1, values 1 and 2, sum 3. Total: 5 + 16 + 3 = 24.
Problem 2: why the edge is stored at the child
Explain why an edge value is stored at the child endpoint of the edge, and what would go wrong if it were stored at the parent endpoint instead.
Show the answer
Hint: count how many edges one parent has, and how many parents one child has.
Answer: each non-root vertex has exactly one parent edge, so storing the edge at the child gives each edge its own slot. A parent can have many child edges, so storing them at the parent would put several edge values in one slot. The sum would then add a value that does not belong to the path, or lose one, when two sibling edges are on the path.
Problem 3: the light-edge bound
What is the largest number of light edges on a path from a vertex to the root, in a tree of 200000 vertices?
Show the answer
Hint: the subtree size at least doubles at each light edge going up. Find the largest k with 2^k at most 200000.
Answer: 17. Since 2^17 = 131072 is at most 200000, and 2^18 = 262144 is more, the bound is floor(log2 200000) = 17.
Problem 4: path update that skips the LCA
Write the code for path_add_vertices_except_lca(u, v, x), which adds x to every vertex on the path except the LCA. Use only the functions in hld.hpp.
Show the answer
Hint: this is the edge query with the same exclusion, applied to the update. The last range starts one position after the LCA.
Answer: add x to the whole path, then take x back off the LCA. The LCA is the only vertex that gets undone.
void path_add_except_lca(HLD& h, int u, int v, long long x) {
int l = h.lca(u, v);
h.path_add(u, v, x);
h.path_add(l, l, -x);
}This is correct because the LCA lies on the path, so it receives x once from path_add and -x once from the second call. It costs two path operations instead of one, which is still O(log^2 n). On the example, with x = 100 on the path 3 to 6, the sum afterwards is 523, which is 23 + 5 * 100 (five vertices change, and the LCA 0 does not). Check it with the naive walk before you use it.
Problem 5: why the stack pushes the heavy child last
In the position loop, the heavy child is pushed last. What breaks if the order is reversed (heavy child pushed first)?
Show the answer
Hint: think about which child is popped next, and where its position comes out.
Answer: a stack pops the last item pushed first. If the heavy child is pushed first, a light child is popped next, so the heavy child's position is no longer pos[v] + 1. Chains would then not be contiguous blocks, and a path query would read the wrong range. The subtree ranges would still be contiguous, because the DFS order is still a DFS, but the chain ranges would break.