Tree Problem Summary

Introduction

During the summer vacation, I systematically studied various operations on trees through Teacher Tuo's sharing and discovered many useful techniques, which I now summarize.

Teacher Tuo is amazing!

One

Problem Type: Batch processing queries of the form f(dep(lca(x,y))), where f(x) is a function of x.
Approach: First perform tree decomposition, then precompute contributions along the path from x to the root (different depths contribute differently, which can be represented in data structures). Then, for each y, compute the sum of contributions along its path to the root.
Principle: The LCA of x and y is the first intersection point of their paths to the root, and its depth corresponds to the length of the overlapping part of these two paths.
Example Problem:

Given m queries, each with l, r, z, find the sum from i=l to r of dep[LCA(i,z)].

——[LNOI2014]LCA

Two

Problem: Handling diameter-related problems on trees.
Key Points:
- For any node, the farthest node is one endpoint of the tree’s diameter (this holds only for trees).
- A tree’s diameter center consists of either one or two nodes.
Example Problem:

q queries, each asking for all possible diameter centers of the minimum connected component formed by a set of nodes.

——2021.8.26 test T2

Three

Problem: Calculating the total weight of all paths, where the weight of a path is the sum of weights of all pairs of nodes on it.
Key Insight: Compute how many times each pair contributes.
- If nodes (x,y) have no ancestor relationship, the count is size[x] * size[y].
- If x is an ancestor of y, the count is (n - size[x] + 1) * size[y].
Principal: Count the number of paths that contain both nodes.
Example Problem:

Each node represents a node in a trie, denoted as S(x). The weight of a path K is:

f(K)=∑_{x∈K,y∈K,x Find the total weight of all paths on the tree.

——Luogu P5439 Eternal

Four

Problem: Processing pairs of nodes with different positional relationships.

Approach:

Pairs with no ancestor-descendant relationship

void dfs(int x, int fa){
	query();
	traverse_subtree;
	insert();
}

Pairs with ancestor-descendant relationship

void dfs(int x, int fa){
	query();
	insert();
	traverse_subtree;
	delete();
}

Example Problem:

Determine whether a tree satisfies ∀1 ≤ i < j ≤ n, gcd(a_i, a_j) = a_{lca(i, j)}.

——Luogu P7854 GCD Tree

Five

Problem: Computing the sum of node weights along paths from multiple nodes to the root without double counting.
Approach: Sort nodes according to DFS order. Compute the sum for each node's path to the root, subtracting the overlaps — the contribution from the LCA of adjacent nodes to the root.
Principle: Similar to virtual tree construction, when nodes are ordered by DFS, overlapping segments are with the LCA of nodes with smaller DFS numbers.
Example Problem:

Using Aho-Corasick automaton to count how many template strings appear in a pattern string (counted once even if repeated).

——[SCOI2012] Naming on the Cat Planet

Six

Problem: Calculating contributions for multiple points to the root path, with multiple queries.
Approach: Offline the problem to each node, traverse the tree once, add contribution upon entering a node, remove upon exiting. This can be viewed as ancestor-descendant pairs.
Note: Non-root paths can be converted into this form using difference techniques, and extended to general paths.
Example Problem:

Given a tree with edges labeled with characters, q queries: for two nodes x, y and a string str, count how many times str appears in the concatenated string of edge labels from x to y.

——2021.7.20 test T2

Seven

Problem: Tree DP where parent DP values depend on child DP values. Need to fix a single node’s DP value and compute the root DP.
Approach: Treat DP transitions as matrices. Traverse the tree, maintain matrix products from root to parent using a stack. For each node, construct a fixed-value matrix and multiply it with the stack top to quickly compute the root DP under fixed conditions.
Example Problem:

A tree where each node joins a set S with probability p(u). If u joins S, it contributes ∑{u∈S} c[v] ∑{v∈S, v∈subtree(u)} s[v]. Choose a binary sequence S to maximize the expected contribution.

——2021.9.13 T3

Eight

Problem: Choosing two key nodes on a tree, each node contributes distance × weight to the nearest key node.
Key Insight: Mark the path from each node to its nearest key node. There exists an edge not marked. Split the tree into two parts and consider contributions separately.
Example Problem:

On a tree, select two key nodes. Each node contributes distance × weight to the nearest key node. Minimize the total contribution (n ≤ 10^3).

——2021.9.16 T4

Nine

Problem: Each node has a color. Multiple queries to count distinct colors in a subtree.
Key Insight: For each color, consider two adjacent nodes in DFS order (x, y). They contribute 1, 1, -1 to x, y, and LCA(x, y) respectively.
Example Problem:

A tree with colored nodes. Mutliple queries: for u, d, count the number of distinct colors in the subtree of u with depth ≤ dep_u + d. Online query.

——BZOJ4771 Colorful Tree

Ten

Problem: For each node x ∈ [1,n], determine how many nodes i ∈ [1,n] satisfy condition p(x,i), where p(x,i) implies p(x,j) = 1 for all j in the subtree of i. Define val_x = sum_{i} [p(x,i) = 1 ∧ p(x,fa_i) = 0], compute val_x for all x.
Key Insight: Eliminate the requirement that the parent must be 0 while the node is 1. Consider a tree with sum_{i=1}^m d_{a_i} = 2m - 1, where d_i is the degree of node i and a_i is a node in the subtree. Thus, 1 = sum_{i=1}^m (2 - d_{a_i}). Assign each node a contribution of 2(2 - d_i). Then, val_x = sum_{i=1}^n [p(x,i) = 1] * (2 - d_i), removing the constraint.
Example Problem:

A tree where each leaf is an entrance/exit. Initially, farmers can be placed at entrences. Both Bessie and farmers move simultaneously. If they meet, Bessie is caught. For node i, determine the minimum number of farmers needed so that Bessie starting at i gets caught.

——P4183 [USACO18JAN] Cow at Large P

Tags: tree dfs LCA dynamic-programming graph-theory

Posted on Sat, 01 Aug 2026 16:21:20 +0000 by D_tunisia

Freaks City