Palindromic Tree (Eertree)

Quick Revisit

• USE WHEN: Counting, enumerating, or running DP over all distinct palindromic substrings
• INVARIANT: Each node = one distinct palindromic substring; suffix link points to the longest proper palindromic suffix of that palindrome
• TIME: O(n) amortized construction (O(1) amortized per character) | SPACE: O(n)
• CLASSIC BUG: Forgetting the two root nodes (length −1 for odd, length 0 for even) — suffix link traversal breaks without them
• PRACTICE: 07-ladder-strings

Online data structure that represents every distinct palindromic substring in $O(n)$ time and space. The go-to when you need to count, enumerate, or run DP over palindromic substrings.

Difficulty: [Advanced]Prerequisites: String Hashing, ManacherCF Rating Range: 1900--2100

---

Contents

• Intuition
• How It Works
• Implementation
• Complexity Analysis
• Common Patterns
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

Intuition

"Count the distinct palindromic substrings of eertree."

Naive plan: check every substring, verify it reads the same forwards and backwards.

  s = "eertree"   (indices 0..6)

  All substrings (21 total, lengths 1..7):
  len 1:  e  e  r  t  r  e  e          check each: O(1)
  len 2:  ee er rt tr re ee             check each: O(2)
  len 3:  eer ert rtr tre ree           check each: O(3)
  len 4:  eert ertr rtre tree           check each: O(4)
  len 5:  eertr ertree rtree            check each: O(5)
  len 6:  eertre ertree                 check each: O(6)
  len 7:  eertree                       check each: O(7)

  Palindromes found: "e", "r", "t", "ee", "rtr"  -->  5 distinct
  Total work: O(n^2) substrings x O(n) palindrome check = O(n^3)
              (O(n^2) with hashing, but still quadratic)

For $n=3\times {10}^5$ this is hopeless. We need a fundamentally different representation.

A palindromic tree has at most $n+2$ nodes (one per distinct palindromic substring plus two roots), and can be built incrementally in amortized $O(n)$ -- each new character adds at most one new palindromic substring.

Why at most one new palindrome per character? When we append character $s[i]$, any new palindrome must end at position $i$. If two new palindromes both end at $i$, the shorter is a suffix of the longer -- but that shorter palindrome was already a suffix of some earlier palindrome (by the palindromic structure), so it was already in the tree. Contradiction. Therefore only the longest new palindrome ending at $i$ is genuinely new.

Analogy: Think of a family tree of palindromes. Each palindrome has a "parent" obtained by stripping one character from each end. The imaginary root (length $-1$) is the ancestor of all single-character palindromes, and the empty-string root (length $0$) is the ancestor of all even-length palindromes. Adding a character is like registering at most one new birth in this family.

Manacher vs. eertree, said clearly

These two tools are easy to confuse because they live in the same chapter and both deal with palindromes, but they answer fundamentally different questions:

Aspect	Manacher	Eertree
What it produces	An array $p[i]$ -- palindrome radius at each position	A tree -- one node per distinct palindromic substring
Granularity	Positions and lengths	Palindromes as first-class objects
Online?	No, needs the whole string up front	Yes, append one character at a time
Best for	"longest palindromic substring", "is $s[l..r]$ a palindrome?", interval queries	"count distinct palindromes", "DP over palindromes", occurrence counts, palindrome factorization
Per-palindrome metadata	None (just the radius array)	Suffix links, occurrence counts, parent pointers
Complexity	$O(n)$ time, $O(n)$ space	$O(n)$ amortized time, $O(n\cdot \sigma )$ space (array)

If a problem talks about positions (radii, ranges, "is this substring a palindrome?"), reach for Manacher. If it talks about palindromes as things you can count, list, or DP over, reach for the eertree.

The two roots, expanded

Most eertree bugs trace back to mishandling the two roots. They look magical but each plays a precise mechanical role:

• The empty root (length $0$). Represents the empty palindrome. Children of this root are palindromes of even length 2: wrapping the empty string with a character $c$ on both sides yields $cc$. Its existence is what unifies even-length palindromes with the rest of the tree.
• The imaginary root (length $-1$). A genuinely virtual node -- there is no length-$(-1)$ string. But its length is exactly what makes the recursion bottom out cleanly: when we look up suffix links from a length-$1$ palindrome, we need to land on something whose "child via $c$" can be a length-$1$ palindrome. The imaginary root fills that role. Children of the imaginary root are palindromes of length $1$: wrapping the length-$(-1)$ string with $c$ on both sides yields $c$ alone (length $-1+2=1$).

The deeper reason the imaginary root works: the palindrome-extension check is $s[i-\text{len}(v)-1]=s[i]$. For $\text{len}(v)=-1$ this becomes $s[i-0]=s[i]$, i.e. $s[i]=s[i]$, which is always true. So the suffix-link walk is guaranteed to terminate -- worst case it falls all the way to the imaginary root, matches trivially, and creates a fresh single-character palindrome.

The two roots have one more subtlety: the imaginary root's suffix link must point to itself (link[0] = 0). That self-loop is the base case for get_link. If you set it to anything else the loop either runs forever or steps onto invalid memory.

With those roles in place, every operation in add() -- the get_link walk from last, the second get_link walk to find the new node's suffix link, the special case of length-$1$ palindromes hanging off the imaginary root and length-$2$ palindromes hanging off the empty root -- becomes mechanical. Treat the two roots as the boundary conditions of the data structure rather than as arbitrary sentinels.

Visual Walkthrough

Build the eertree for $s = $ "abba", character by character.

Initial state -- two root nodes, no palindromes yet:

  Nodes:  [root -1] len=-1    [root 0] len=0
          (imaginary root)     (empty string)
  Suffix link: root 0 --> root -1
               root -1 --> root -1 (self)
  last = root 0

Step 1: append 'a' ($i=0$)

  Walk from last = root 0 (len=0):
    Need s[i - len - 1] == s[i], i.e. s[-1] == s[0]  -->  out of bounds
    Follow suffix link to root -1 (len=-1):
    Need s[i - (-1) - 1] == s[i], i.e. s[0] == s[0]  -->  match!

  root -1 has no child 'a'  -->  CREATE node "a" (len = -1 + 2 = 1)
  Suffix link of "a": length 1, so link = root 0
  last = "a"

  Tree edges:              Suffix links:
       [root -1]              "a" ----> root 0
          |
         'a'
          |
       [ "a" ]
        len=1

Step 2: append 'b' ($i=1$)

  Walk from last = "a" (len=1):
    s[i - 1 - 1] = s[-1]  -->  out of bounds, follow link to root 0
  Walk from root 0 (len=0):
    s[i - 0 - 1] = s[0] = 'a' != s[1] = 'b'  -->  follow link to root -1
  Walk from root -1 (len=-1):
    s[1] == s[1]  -->  match!

  root -1 has no child 'b'  -->  CREATE node "b" (len=1)
  Suffix link of "b": length 1, so link = root 0
  last = "b"

  Tree edges:              Suffix links:
       [root -1]              "a" ----> root 0
       /      \               "b" ----> root 0
     'a'      'b'
     /          \
  [ "a" ]    [ "b" ]
   len=1      len=1

Step 3: append 'b' ($i=2$)

  Walk from last = "b" (len=1):
    s[i - 1 - 1] = s[0] = 'a' != s[2] = 'b'  -->  follow link to root 0
  Walk from root 0 (len=0):
    s[i - 0 - 1] = s[1] = 'b' == s[2] = 'b'  -->  match!

  root 0 has no child 'b'  -->  CREATE node "bb" (len = 0 + 2 = 2)
  Suffix link of "bb": follow from root 0's link = root -1
    root -1 has child 'b' = node "b"  -->  link = "b"
  last = "bb"

  Tree edges:                           Suffix links:
       [root -1]       [root 0]           "a"    ----> root 0
       /      \            |               "b"    ----> root 0
     'a'      'b'        'b'              "bb"   ----> "b"
     /          \          |
  [ "a" ]    [ "b" ]   [ "bb" ]
   len=1      len=1      len=2

Step 4: append 'a' ($i=3$)

  Walk from last = "bb" (len=2):
    s[i - 2 - 1] = s[0] = 'a' == s[3] = 'a'  -->  match!

  "bb" has no child 'a'  -->  CREATE node "abba" (len = 2 + 2 = 4)
  Suffix link of "abba": follow from "bb"'s link = "b" (len=1)
    s[i - 1 - 1] = s[1] = 'b' != s[3] = 'a'  -->  follow link to root 0
    s[i - 0 - 1] = s[2] = 'b' != s[3] = 'a'  -->  follow link to root -1
    root -1 has child 'a' = node "a"  -->  link = "a"
  last = "abba"

  FINAL TREE:
  +-----------+                     +-----------+
  | root -1   |                     |  root 0   |
  | len = -1  |                     |  len = 0  |
  +-----+-----+                    +-----+-----+
       / \                               |
     'a'  'b'                           'b'
     /      \                            |
  +---+   +---+                     +----+----+
  |"a"|   |"b"|                     |  "bb"   |
  | 1 |   | 1 |                     |  len=2  |
  +---+   +---+                     +----+----+
                                         |
                                        'a'
                                         |
                                    +----+----+
                                    | "abba"  |
                                    |  len=4  |
                                    +---------+

  Suffix links:  "a" -> root 0,  "b" -> root 0
                 "bb" -> "b",    "abba" -> "a"

  Distinct palindromes: "a", "b", "bb", "abba"  -->  4
  (= number of nodes - 2 roots = 6 - 2 = 4)

The Invariant

Each node represents exactly one distinct palindromic substring. The suffix link of node $v$ points to the longest proper palindromic suffix of the palindrome represented by $v$. After processing $s[0..i]$, the pointer last points to the node of the longest palindromic suffix of $s[0..i]$.

This invariant guarantees:

• Completeness: every distinct palindromic substring appears as a node.
• Uniqueness: no two nodes represent the same substring.
• Online construction: we can extend the string one character at a time, and the tree stays consistent.

What the Code Won't Teach You

The $O(\log n)$ palindromic suffix decomposition. Every prefix of a string has at most $O(\log n)$ distinct palindromic suffix lengths. This non-obvious structural property -- provable via the series decomposition -- is what makes the palindrome factorization DP run in $O(n\log n)$ rather than $O(n^2)$. The code builds the tree, but doesn't explain why the suffix-link chain is short enough to traverse efficiently.

Why len = -1 is the secret anchor. The imaginary root (length $-1$) seems like a hack. It's actually the key to correctness: when you check $s[i-\text{len}(v)-1]=s[i]$ for the imaginary root, you get $s[i-(-1)-1]=s[i]$, i.e., $s[i]=s[i]$ -- always true. This guarantees the suffix-link walk always terminates by creating at least a single-character palindrome. Remove or change this root and the algorithm fails on the very first character.

Eertree vs. Manacher: different questions, different tools. Manacher answers "what is the palindrome radius at each position?" The eertree answers "what are the distinct palindromic substrings as objects?" If you need palindrome positions and lengths for interval queries, use Manacher. If you need palindromes as countable, enumerable entities for DP or combinatorics, use the eertree. They are complementary, not interchangeable.

The magical $n+2$ bound. A string of length $n$ has at most $n+1$ distinct palindromic substrings (including the empty string). This is a deep combinatorial fact -- not obvious at all -- and it's what makes the eertree practical. It means the tree never has more than $O(n)$ nodes regardless of the input. The proof goes through the observation that each new character adds at most one new palindrome. Once you know this, the online construction becomes intuitive: process each character, check if its longest palindromic suffix is already in the tree, and insert at most one new node.

Series links are the hidden weapon for palindrome factorization. The basic eertree gives you suffix links, but the series link optimization is what makes palindrome-partition DP fast. A "series" is a maximal chain of nodes whose palindromes differ by the same period (e.g., "aba", "ababa", "abababa"). Within a series, the DP values follow an arithmetic pattern, so you can jump to the series head and compute the contribution in $O(1)$ instead of walking the entire suffix-link chain. This drops palindrome factorization from $O(n^2)$ to $O(n\log n)$ -- and it's the technique behind problems like "minimum number of palindromes to partition a string."

The common implementation trap: forgetting to propagate counts. After building the eertree, occurrence counts of each palindrome are stored only for the longest palindromic suffix at each position. To get the total occurrence count of every distinct palindrome, you must propagate counts up the suffix-link tree in reverse insertion order: cnt[link[v]] += cnt[v]. This is a one-line fix, but forgetting it means you're only counting "rightmost" occurrences, silently underreporting by a factor that depends on the input.

When to Reach for This

Trigger phrase in problem statement	Why eertree?
"count distinct palindromic substrings"	Exactly what node count gives
"enumerate all palindromic substrings"	Nodes = the enumeration
"number of palindromic substrings (with repeats)"	Propagate occurrence counts through suffix links
"palindrome factorization / partition"	DP on suffix links with series-link optimization
"longest palindromic suffix of each prefix"	last pointer after each add()
"max(occurrences $\times$ length) over palindromes"	Propagate counts, scan all nodes

  Suffix-link chain for "abaab" after full construction:

  Suffix links form a tree rooted at the imaginary root:

       [root -1]  (len = -1, always-match anchor)
          │
     ┌────┴────┐
     │         │
   [root 0]  ["a"]  (len = 1)
   (len=0)     │
               ├──────┐
               │      │
            ["aba"]  ["aa"] (len = 2)
            (len=3)    │
                     ["abaab"]?  <- depends on full string
                     
  Walking suffix links from any node always reaches
  root -1 in O(depth) steps. Depth <= O(log n) for
  the series-link shortcut.

Rule of thumb: if Manacher gives you positions but you need distinct palindromes as objects, reach for the eertree.

---

3. How It Works

Structure

The eertree has two types of links:

1. Tree edges (children[c]): node $v$ has a child labeled $c$ meaning: if $v$ represents palindrome $P$, the child represents $cPc$ (wrap $P$ with character $c$ on both sides).

2. Suffix links (link): node $v$ points to the node representing the longest proper palindromic suffix of $v$'s palindrome.

Two special roots:

• Imaginary root (length $-1$): conceptual parent of all single-character palindromes. Adding character $c$ on both sides of a length-$(-1)$ string gives a length-$1$ string $c$.
• Empty root (length $0$): represents the empty palindrome. Adding $c$ on both sides gives $cc$ (length $2$).

Incremental Construction

To append character $s[i]$:

1. Find the right parent. Starting from last, walk up suffix links until we find node $v$ where $s[i-\text{len}(v)-1]=s[i]$. This means $s[i]\cdot \text{palindrome}(v)\cdot s[i]$ exists in $s[0..i]$.

2. Check if the child exists. If $v$ already has child $s[i]$, that palindrome was seen before -- just update last and increment its occurrence counter.

3. Create new node. Otherwise, create node $u$ with $\text{len}(u)=\text{len}(v)+2$.

4. Compute suffix link. From $v$'s suffix link, walk up again to find the next node $w$ where $s[i-\text{len}(w)-1]=s[i]$. Set $u.\text{link}=w.\text{children}[s[i]]$ (which must exist or be the empty root for length-$1$ nodes).

5. Update last to the (possibly new) node.

The "walk up suffix links" in steps 1 and 4 is amortized $O(1)$ over the entire construction (the last pointer can only jump down by 1 per character, and walking up is charged to previous jumps).

---

Implementation

4a. Clean Version (Map-Based)

Readable and sufficient for most contest constraints ($n\le {10}^5$).

#include <bits/stdc++.h>
using namespace std;

struct EerTree {
    struct Node {
        int len, link, cnt;
        map<int, int> ch;
    };

    vector<Node> t;
    string s;
    int last;

    EerTree() : last(1) {
        t.push_back({-1, 0, 0, {}});   // node 0: imaginary root
        t.push_back({ 0, 0, 0, {}});   // node 1: empty root
    }

    int get_link(int v, int i) {
        while (i - 1 - t[v].len < 0 || s[i - 1 - t[v].len] != s[i])
            v = t[v].link;
        return v;
    }

    bool add(char c) {
        s += c;
        int i = (int)s.size() - 1;
        int cur = get_link(last, i);
        int cc = c - 'a';
        if (t[cur].ch.count(cc)) {
            last = t[cur].ch[cc];
            t[last].cnt++;
            return false;          // no new palindrome
        }
        int now = (int)t.size();
        t.push_back({t[cur].len + 2, 0, 1, {}});
        int lnk = get_link(t[cur].link, i);
        t[now].link = t[lnk].ch.count(cc) ? t[lnk].ch[cc] : 1;
        t[cur].ch[cc] = now;
        last = now;
        return true;               // new palindrome created
    }

    // Propagate occurrence counts down suffix links (call once after all adds).
    void propagate() {
        for (int i = (int)t.size() - 1; i >= 2; i--)
            t[t[i].link].cnt += t[i].cnt;
    }

    int distinct() { return (int)t.size() - 2; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    EerTree pt;
    for (char c : s) pt.add(c);
    cout << pt.distinct() << "\n";
}

4b. Optimized Version (Array-Based, $O(n)$ Time)

For tight constraints ($n\le 3\times {10}^5$, small alphabet). Replaces map with a fixed-size array.

#include <bits/stdc++.h>
using namespace std;

struct EerTree {
    static constexpr int ALPHA = 26;

    struct Node {
        int len, link, cnt;
        int ch[ALPHA];
    };

    vector<Node> t;
    string s;
    int last;

    EerTree() : last(1) {
        t.push_back({-1, 0, 0, {}});
        t.push_back({ 0, 0, 0, {}});
        fill(t[0].ch, t[0].ch + ALPHA, -1);
        fill(t[1].ch, t[1].ch + ALPHA, -1);
    }

    void reserve(int n) { t.reserve(n + 2); }

    int get_link(int v, int i) {
        while (i - 1 - t[v].len < 0 || s[i - 1 - t[v].len] != s[i])
            v = t[v].link;
        return v;
    }

    bool add(char c) {
        s += c;
        int i = (int)s.size() - 1;
        int cur = get_link(last, i);
        int cc = c - 'a';
        if (t[cur].ch[cc] != -1) {
            last = t[cur].ch[cc];
            t[last].cnt++;
            return false;
        }
        int now = (int)t.size();
        t.push_back({t[cur].len + 2, 0, 1, {}});
        fill(t[now].ch, t[now].ch + ALPHA, -1);
        int lnk = get_link(t[cur].link, i);
        t[now].link = (t[lnk].ch[cc] != -1) ? t[lnk].ch[cc] : 1;
        t[cur].ch[cc] = now;
        last = now;
        return true;
    }

    void propagate() {
        for (int i = (int)t.size() - 1; i >= 2; i--)
            t[t[i].link].cnt += t[i].cnt;
    }

    int distinct() { return (int)t.size() - 2; }
};

4c. With Series Links (For Palindrome Factorization DP)

Adds diff and series_link fields for amortized $O(n)$ palindrome partitioning.

struct EerTree {
    static constexpr int ALPHA = 26;

    struct Node {
        int len, link, cnt;
        int diff;          // len - link.len
        int series_link;   // longest suffix u with diff[u] != diff[v]
        int dp;            // auxiliary DP value for palindrome factorization
        int ch[ALPHA];
    };

    vector<Node> t;
    string s;
    int last;

    EerTree() : last(1) {
        t.push_back({-1, 0, 0, 0, 0, 0, {}});
        t.push_back({ 0, 0, 0, 0, 0, 0, {}});
        fill(t[0].ch, t[0].ch + ALPHA, -1);
        fill(t[1].ch, t[1].ch + ALPHA, -1);
    }

    int get_link(int v, int i) {
        while (i - 1 - t[v].len < 0 || s[i - 1 - t[v].len] != s[i])
            v = t[v].link;
        return v;
    }

    bool add(char c) {
        s += c;
        int i = (int)s.size() - 1;
        int cur = get_link(last, i);
        int cc = c - 'a';
        if (t[cur].ch[cc] != -1) {
            last = t[cur].ch[cc];
            t[last].cnt++;
            return false;
        }
        int now = (int)t.size();
        t.push_back({t[cur].len + 2, 0, 1, 0, 0, 0, {}});
        fill(t[now].ch, t[now].ch + ALPHA, -1);
        int lnk = get_link(t[cur].link, i);
        t[now].link = (t[lnk].ch[cc] != -1) ? t[lnk].ch[cc] : 1;
        t[cur].ch[cc] = now;

        t[now].diff = t[now].len - t[t[now].link].len;
        if (t[now].diff == t[t[now].link].diff)
            t[now].series_link = t[t[now].link].series_link;
        else
            t[now].series_link = t[now].link;

        last = now;
        return true;
    }
};

---

Complexity Analysis

Operation	Time	Space
Build eertree for string of length $n$	$O(n)$ amortized (array) / $O(n\log \sigma )$ (map)	$O(n\cdot \sigma )$ (array) / $O(n)$ (map)
add(c) single character	$O(1)$ amortized	$O(\sigma )$ per new node
propagate()	$O(n)$	$O(1)$ extra
Count distinct palindromes	$O(1)$ after build	--

Why $O(n)$ amortized for construction: The pointer last moves to a deeper node by at most 1 per add(). Each step of get_link moves to a strictly shallower node (shorter suffix link). Over $n$ operations, total upward movement $\le$ total downward movement $=n$. Hence total get_link steps across all add() calls is $O(n)$.

  Amortized cost of get_link traversal:

  Character:   a    b    b    a
  last depth:  1    1    2    3     (depth = node depth in tree)
               ↓    ↓    ↓    ↓
  get_link     1    2    1    1     (suffix-link steps this call)
  steps:

  Total depth increase: +1 +0 +1 +1 = 3
  Total get_link steps:  1 +2 +1 +1 = 5
  
  Over n characters: total steps <= 2n (each step up
  cancels a previous step down). Amortized O(1) per add().

Node count bound: at most $n+2$ nodes. Proof: each add() creates at most one node, plus the 2 roots.

---

Common Patterns

Pattern 1: Count Distinct Palindromic Substrings

Direct readout: eertree.distinct() = number of nodes $-2$.

EerTree pt;
for (char c : s) pt.add(c);
cout << pt.distinct() << "\n";

For online variant (distinct count after each prefix), track the running total:

int total = 0;
for (char c : s) {
    total += pt.add(c);  // add() returns 1 if a new palindrome was created
    cout << total << " \n"[&c == &s.back()];
}

Problems: CF 835D, SPOJ NUMOFPAL

Pattern 2: Count Total Palindromic Substrings (With Repetitions)

Each node $v$ has an occurrence count: how many times that palindrome appears as a substring. After propagate(), $v.\text{cnt}$ is the total occurrence count. Sum them for the total.

EerTree pt;
for (char c : s) pt.add(c);
pt.propagate();
long long total = 0;
for (int i = 2; i < (int)pt.t.size(); i++)
    total += pt.t[i].cnt;
cout << total << "\n";

Why propagate? During construction, cnt only counts positions where $v$ is the longest palindromic suffix. But $v$ also occurs wherever any descendant (via suffix links) occurs. Propagating in reverse order (longest to shortest) accumulates the true count.

Problems: CF 245H

  Propagation of occurrence counts through suffix links:

  Before propagation:          After propagation:
  (only "last" positions)      (true occurrence counts)

  "abba"  cnt=1                "abba"  cnt=1
     │ suffix link                │
  "a"     cnt=1                "a"     cnt=1+1 = 2  <- "a" appears
     │                            │                    inside "abba"
  root 0  cnt=0                root 0  cnt=0+2 = 2

  Traverse nodes longest->shortest (reverse creation order).
  Each node adds its cnt to its suffix-link parent.
  Result: cnt[v] = total occurrences of palindrome v.

Pattern 3: Maximize occurrences $\times$ length

Classic: find the palindromic substring maximizing $\text{cnt}(v)\times \text{len}(v)$.

EerTree pt;
for (char c : s) pt.add(c);
pt.propagate();
long long ans = 0;
for (int i = 2; i < (int)pt.t.size(); i++)
    ans = max(ans, (long long)pt.t[i].cnt * pt.t[i].len);
cout << ans << "\n";

Problems: APIO 2014 Palindrome

Pattern 4: Palindrome Factorization (Minimum Palindrome Partition)

Given string $s$, find the minimum number of palindromes that concatenate to form $s$.

Use DP: $f[i] = $ minimum palindromes to partition $s[0..i-1]$. For each position $i$, walk suffix links from last using series links to jump in $O(\log n)$ amortized.

EerTree pt;
int n = s.size();
vector<int> f(n + 1, n + 1);
f[0] = 0;

for (int i = 0; i < n; i++) {
    pt.add(s[i]);
    // Walk the suffix-link chain using series links for speed
    for (int v = pt.last; v > 1; v = pt.t[v].series_link) {
        // The series of palindromes ending at position i with the same "diff"
        // starts at v and follows suffix links while diff stays the same.
        // The key position for the DP transition:
        int j = i + 1 - t[t[v].series_link].len - t[v].diff;
        pt.t[v].dp = f[j];
        if (t[v].diff == t[t[v].link].diff)
            pt.t[v].dp = min(pt.t[v].dp, pt.t[t[v].link].dp);
        f[i + 1] = min(f[i + 1], pt.t[v].dp + 1);
    }
}
cout << f[n] << "\n";

The series-link optimization ensures each position contributes $O(1)$ amortized to the total suffix-link traversal, keeping the overall DP at $O(n)$.

Problems: CF 906E

Pattern 5: Longest Palindromic Suffix of Each Prefix

After each add(s[i]), the node last represents the longest palindromic suffix of $s[0..i]$.

EerTree pt;
for (int i = 0; i < (int)s.size(); i++) {
    pt.add(s[i]);
    cout << pt.t[pt.last].len << " \n"[i + 1 == (int)s.size()];
}

Problems: CF 1326D2

---

Contest Cheat Sheet

+-------------------------------------------------------------------+
|              PALINDROMIC TREE (EERTREE) CHEAT SHEET                |
+-------------------------------------------------------------------+
| WHEN TO USE:                                                       |
|   o Count / enumerate distinct palindromic substrings              |
|   o DP over palindromic substrings (partition, factorization)      |
|   o Online: answer queries as characters are appended              |
|   o Need palindromes as "objects" (not just positions)             |
+-------------------------------------------------------------------+
| STRUCTURE:                                                         |
|   2 roots: imaginary (len=-1), empty (len=0)                      |
|   Each node = one distinct palindrome, children = wrap with char   |
|   Suffix link = longest proper palindromic suffix                  |
|   At most n+2 nodes total                                          |
+-------------------------------------------------------------------+
| CORE:                                                              |
|   get_link(v, i):                                                  |
|     while s[i-1-len[v]] != s[i]: v = link[v]                      |
|     return v                                                       |
|   add(c): cur = get_link(last,i)                                   |
|     if cur.ch[c] exists: last = cur.ch[c], return                  |
|     create node, set suffix link via get_link(cur.link,i)          |
|     last = new node                                                |
+-------------------------------------------------------------------+
| AFTER BUILD:                                                       |
|   propagate() to get true occurrence counts                        |
|   distinct = num_nodes - 2                                         |
+-------------------------------------------------------------------+
| COMPLEXITY: O(n) time, O(n * sigma) space                          |
+-------------------------------------------------------------------+

---

Gotchas & Debugging

Forgetting to propagate before reading counts

• cnt after construction only reflects positions where a palindrome is the longest palindromic suffix. Call propagate() to accumulate the true occurrence count through suffix links. Missing this gives undercounts on virtually every count-based problem.

Off-by-one in get_link

• The condition i - 1 - t[v].len < 0 guards against accessing $s[-1]$. If you write i - t[v].len - 1 in a different order and the types are unsigned, you get wraparound instead of a negative check. Use signed int throughout.

Imaginary root self-link

• Node $0$ (imaginary root, len $=-1$) must have link = 0 (points to itself). If you set it to $1$ or $-1$, the suffix-link walk in get_link either loops forever or segfaults.

Map vs array children

• With map<int,int>, lookups are $O(\log \sigma )$ per step. For large alphabets (e.g., integers mod something), this is fine. For 26-letter lowercase, the array version avoids constant-factor overhead that can cause TLE on $n=3\times {10}^5$.
• When using arrays, initialize children to $-1$ (not $0$, since $0$ is a valid node index -- the imaginary root).

Series-link DP correctness

• In palindrome factorization, the dp field stored on each node is not reset between test cases. If your problem has multiple test cases, either rebuild the eertree or clear the dp fields.

Confusing "new palindrome" with "new occurrence"

• add() returns true only when a brand-new palindromic substring is discovered. Existing palindromes get their cnt incremented but add() returns false. Don't conflate the two in counting logic.

Debugging tip

• Print each node's (id, len, link, cnt) after construction. Verify node count matches the expected number of distinct palindromic substrings on small inputs. The suffix-link tree should be a valid tree rooted at the imaginary root (every node reachable via suffix links eventually reaches root).

Mental Traps

Trap 1: "The eertree is just a trie of palindromes."

It's fundamentally different. In a trie, each edge appends one character to one end. In the eertree, each edge wraps a palindrome with a character on both sides ($c\cdot P\cdot c$). The eertree also has suffix links -- without them, the construction doesn't know where to attach new palindromes. Thinking "trie" leads you to expect $O(n^2)$ nodes (like a suffix trie), when the eertree guarantees at most $n+2$.

  Trie of palindromes of "abba":     Eertree of "abba":
  (would store each as a path)       (wraps both sides per edge)

       root                          [root -1]     [root 0]
      / | \                           /     \          |
     a  b  ...                      'a'    'b'       'b'
     |  |                            |      |         |
     b  b                          ["a"]  ["b"]    ["bb"]
     |  |                          len=1  len=1    len=2
     b  a                                            |
     |                                              'a'
     a                                               |
     (4 paths for 4 palindromes)                 ["abba"]
                                                  len=4
                                    
  Trie: O(sum of lengths) nodes     Eertree: exactly 6 nodes
                                    (4 palindromes + 2 roots)

Trap 2: "I can use Manacher for everything the eertree does."

Manacher gives you a radius array -- positions and lengths. The eertree gives you palindromic substrings as first-class objects with parent pointers, occurrence counts, and suffix links. For "count distinct palindromic substrings," the eertree is one line (tree.size() - 2). For "palindrome factorization DP," only the eertree's series-link structure gives amortized $O(n)$. They answer different questions.

---

Common Mistakes

1. Missing imaginary root boundary handling. "My eertree built correctly but the palindrome DP gave wrong answers on certain inputs..." The issue was in the get_link function: checking s[i - len - 1] without handling the boundary case when i - len - 1 < 0. The imaginary root (length $-1$) exists precisely to handle this -- its length of $-1$ ensures that i - (-1) - 1 = i, which is always valid. Make sure the imaginary root is set up before the first insertion, and that get_link uses it as the ultimate fallback.

Debug Drills

Drill 1 -- Wrong suffix link for new palindrome node

int new_link = get_link(tree[cur].suf, i);
tree[++sz].suf = tree[new_link].children[c];  // BUG

What's wrong?

The suffix link of the new node should be the child of get_link(tree[cur].suf, i) for character c, not get_link itself. But you also need to handle the case where that child doesn't exist (it should be the empty root). Correct:

int lnk = get_link(tree[cur].suf, i);
tree[++sz].suf = tree[lnk].children.count(c) ? tree[lnk].children[c] : 1; // 1 = empty root

Actually, the suffix link should be set after checking if the palindrome already exists. The order matters: find parent via get_link(last, i), check if child exists, and only if creating a new node, compute its suffix link via get_link(tree[parent].suf, i).

Drill 2 -- Not propagating counts in reverse order

for (int v = 2; v <= sz; v++)
    tree[tree[v].suf].cnt += tree[v].cnt;

What's wrong?

Propagation must go from the last-created node to the first (reverse insertion order), not from 2 to sz. Nodes created later may have suffix links to earlier nodes, so forward iteration misses contributions:

for (int v = sz; v >= 2; v--)
    tree[tree[v].suf].cnt += tree[v].cnt;

Drill 3 -- Imaginary root length set to 0 instead of -1

tree[0].len = 0;  // imaginary root
tree[1].len = 0;  // empty string root
tree[1].suf = 0;

What's wrong?

The imaginary root (node 0) must have len = -1, not len = 0. With len = 0, the get_link check s[i - len - 1] == s[i] becomes s[i - 1] == s[i], which fails for the first character (index out of bounds) and breaks the base case. Fix: tree[0].len = -1;

---

Self-Test

Before moving to problems, verify you can do these without looking at the notes:

• [ ] Explain the purpose of the two root nodes (length $-1$ and length $0$) and why length $-1$ guarantees the suffix-link walk always terminates
• [ ] Hand-trace eertree construction for "abba" step by step: which node is created, what its suffix link is, and why
• [ ] Distinguish node count (distinct palindromic substrings = nodes $-2$) from total occurrence count (requires propagation through suffix links)
• [ ] Describe the propagation step: traverse in reverse creation order, add each node's count to its suffix-link parent
• [ ] Name two problems where the eertree is the natural tool and two where Manacher or hashing is simpler

---

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Know that at most $n+1$ distinct palindromic substrings exist.
1500	Build an eertree and count distinct palindromic substrings of a string.
1800	Use series links for palindrome factorization DP (e.g., minimum palindrome partition).
2100	Combine eertree with other structures (hashing, segment tree) for advanced palindrome queries.

#	Problem	Source	Difficulty	Key Idea
1	Number of Palindromes	SPOJ	1600	Direct: count distinct palindromic substrings
2	Palindromic Characteristics	CF 835D	1900	$k$-palindrome counting via eertree suffix links
3	Palindrome Degree	CF 7D	1900	Recursive palindrome property, eertree or Manacher
4	Prefix-Suffix Palindrome	CF 1326D2	1800	Longest palindromic suffix/prefix via eertree
5	Palindrome	APIO 2014	2100	Maximize $\text{cnt}\times \text{len}$; propagate counts
6	Palindrome Pairs	CF 17E	2400	Eertree + combinatorics on occurrence positions
7	Palindrome Partition	CF 906E	2600	Eertree + series-link DP for palindrome factorization
8	Palindromic Magic	CF 1081H	2600	Advanced eertree + DP on two strings
9	String Theory	CodeChef	2200	Palindromic substrings with constraints
10	Queries for Palindromes	CF 245H	1800	DP + eertree for range palindrome counting
11	Longest Palindrome	CSES	1700	Find longest palindromic substring
12	Palindrome Queries	CSES	2000	Check if substring is palindrome after updates (hashing approach, but eertree intuition helps)

---

Further Reading

• cp-algorithms: Palindromic Tree -- full derivation, series links, complexity proof
• Mikhail Rubinchik's original paper (2015) -- the inventor's description of the eertree
• CF Blog: Palindromic Tree tutorial -- community walkthrough with implementation details
• Adilet's blog: Palindromic Tree -- visual explanation with animations

Related guidebook entries:

• String Hashing -- combine with eertree for cross-string palindrome matching
• Manacher -- when you need palindrome radii at positions, not distinct palindromes as objects
• Suffix Array -- alternative for some palindrome enumeration problems