DSU on Tree

Introduction

DSU on tree answers many subtree queries by deciding which child's data should remain in memory. It is also called the sack technique.

The method is different from ordinary DSU. There are no disjoint-set unions. The shared idea is that large information is kept while small information is rebuilt or merged around it.

Problem or motivation

Every vertex of a rooted tree has a color. For each vertex $v$ , consider its subtree. Find the maximum color frequency in that subtree, then output the sum of all color numbers having that frequency.

For example, if the subtree colors are $[1,2,2,3,3]$ , the maximum frequency is two and the answer is $2+3=5$ .

Introduction

Problem or motivation

Heavy Paths

Naive approach

Core concept

Main algorithm

Mental model and detailed walkthrough

Implementation

Common mistakes

Complexity