CF 207C3 - Game with Two Trees

Rating: 2700
Tags: data structures
Solve time: 2m 32s
Verified: no

Solution

Problem Understanding

We maintain two rooted trees. Initially each tree contains only the root vertex 1.

Every operation adds one new vertex to one of the trees. The new vertex becomes a child of an existing vertex, and the connecting edge stores one lowercase letter.

For any vertex in the first tree, there is exactly one path from that vertex back to the root. Reading edge labels upward gives a string. For example, if the path is:

u --a--> p --b--> root

then the backward string of u is "ab".

For any pair of vertices (j, q) in the second tree where j is an ancestor of q, the downward path from j to q also produces a string.

A triple (i, j, q) is good if:

the backward string of vertex i in tree 1,
equals the forward string from j to q in tree 2.

After every insertion we must print the total number of good triples.

The difficult part is that the trees grow online, and n is up to 100000. Any solution that recomputes all strings after each operation is immediately impossible.

Suppose we try brute force. After n operations both trees may contain O(n) vertices. The number of ancestor-descendant pairs in tree 2 alone can already reach O(n^2), for example when the tree is a chain. Comparing every such path against every vertex in tree 1 becomes cubic in the worst case.

Even storing explicit strings is dangerous. A single path may have length 100000, so repeatedly copying strings would already exceed the time limit.

The key hidden structure is that every relevant object is really just a root-to-vertex string.

For a vertex u in tree 1:

its backward string is exactly the root-to-u string.

For a pair (j, q) in tree 2:

the forward string from j to q is exactly the suffix of the root-to-q string obtained after removing the prefix for j.

This turns the problem into counting equal strings among prefixes and suffixes of root paths.

A subtle edge case appears when the matching string is empty.

Example:

1
1 1 a

The only good triple is (1,1,1) because both strings are empty. The newly added vertex in tree 1 does not create any additional match since tree 2 still has no non-empty paths.

A careless implementation that forgets empty strings would output 0 instead of 1.

Another easy mistake is counting arbitrary paths in tree 2 instead of ancestor-descendant paths.

Example:

Tree 2 contains vertices:

2 with string "a"
3 with string "b"

There is no path producing "ab" because siblings are unrelated. Only ancestor-descendant chains matter.

A third subtle issue is duplicate strings.

Example:

Tree 2 contains two distinct paths with string "a", namely (1,2) and (1,3).

Tree 1 also contains two vertices with backward string "a".

The correct answer after the last operation is:

because each of the two vertices in tree 1 matches both paths in tree 2. We must count multiplicities, not distinct strings.

Approaches

The brute-force solution follows the definition directly.

For every operation:

enumerate every vertex i in tree 1,
compute its backward string,
enumerate every ancestor-descendant pair (j,q) in tree 2,
compare the strings.

This is correct because it literally checks every valid triple. The problem is the cost.

If both trees become chains of length 100000, then tree 2 contains about 5 * 10^9 ancestor-descendant pairs. Even generating them is impossible.

We need a way to count matching strings without explicitly materializing every path.

The crucial observation is that every relevant string corresponds to some root-to-vertex path.

Let:

S(u) be the string on the path from the root to vertex u.

Then:

the backward string for a vertex in tree 1 is exactly S(u),
the forward string from ancestor j to descendant q in tree 2 is a suffix of S(q).

Suppose we process a new vertex v added to tree 2 with edge character c.

Every new good path ending at v corresponds to some ancestor a of v. The produced string is:

suffix of S(v)

More concretely, if x is the child of a on the path toward v, then the produced string equals S(x..v).

We need to know how many vertices in tree 1 currently have exactly that string.

This immediately suggests a trie-like view. Every root-to-vertex string is formed by appending one character to the parent's string. Since all strings come from rooted trees, the set of strings itself forms a trie.

Now consider the reverse process.

If we process tree 2 additions, and walk upward from the new vertex toward the root, we enumerate all suffixes of its root string. For each suffix we want the number of occurrences in tree 1.

The symmetric process happens when adding a vertex to tree 1.

The remaining challenge is complexity. Walking all ancestors per operation is still quadratic on chains.

The missing insight is to use suffix links exactly like the Aho-Corasick automaton.

The collection of all strings appearing in both trees forms one trie. Every vertex corresponds to one trie node. The suffix link of a node points to the longest proper suffix that also exists in the trie.

Then:

all suffixes of a string are obtained by repeatedly following suffix links,
every operation becomes walking through the suffix-link chain.

The total complexity becomes linear because each trie node is created once and each suffix-link transition is processed amortized once.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n³) worst case	O(n²)	Too slow
Optimal	O(n) amortized	O(n)	Accepted

Algorithm Walkthrough

Build one global trie containing every root-to-vertex string from both trees.

Each node stores:

transitions by characters,
suffix link,
how many vertices from tree 1 end here,
how many tree-2 paths correspond to this node.

Represent every vertex in both trees by its corresponding trie node.

If a vertex extends parent p with character c, then its trie node is the transition from trie node of p by c.

If that transition does not exist yet, create it. 3. Compute the suffix link for every newly created trie node.

Suppose the parent trie node is u, and the edge character is c.

The suffix link is obtained by following suffix links from u until we find a node having transition c.

This is exactly the standard Aho-Corasick construction. 4. Maintain two counters for every trie node.

cnt1[x] means how many vertices in tree 1 have exact string represented by node x.

cnt2[x] means how many ancestor-descendant paths in tree 2 produce that string. 5. When inserting a new vertex into tree 1:

Let its trie node be v.

This creates one new backward string equal to the string of v.

Every matching path in tree 2 already counted in cnt2[v] forms a new good triple.

Add cnt2[v] to the answer.

Then increment cnt1[v]. 6. When inserting a new vertex into tree 2:

Let its trie node be v.

Every suffix of the string of v corresponds to one ancestor-descendant path ending at this vertex.

We enumerate all suffixes by repeatedly following suffix links starting from v. 7. For every node x on that suffix-link chain:

increment cnt2[x] because one new path produces this string,
add cnt1[x] to the answer because every tree-1 vertex with the same string forms a new good triple.

Print the running answer after every operation.

Why it works

Each trie node corresponds to exactly one string.

A vertex in tree 1 contributes exactly one string, its root-to-vertex path string. We count it in cnt1 of the corresponding trie node.

A path in tree 2 contributes exactly one suffix of some root string. Following suffix links enumerates all suffixes of that root string exactly once, so every valid ancestor-descendant path is counted once.

Whenever a tree-1 string and a tree-2 path string are equal, they map to the same trie node. The algorithm adds their multiplicities together through cnt1 and cnt2, so every good triple is counted exactly once.

Python Solution

import sys
from collections import deque

input = sys.stdin.readline

class Node:
    __slots__ = ("next", "link", "cnt1", "cnt2")

    def __init__(self):
        self.next = {}
        self.link = 0
        self.cnt1 = 0
        self.cnt2 = 0

nodes = [Node()]

def add_child(parent, ch):
    if ch in nodes[parent].next:
        return nodes[parent].next[ch]

    v = len(nodes)
    nodes.append(Node())
    nodes[parent].next[ch] = v

    if parent == 0:
        nodes[v].link = 0
    else:
        p = nodes[parent].link
        while p and ch not in nodes[p].next:
            p = nodes[p].link

        if ch in nodes[p].next:
            nodes[v].link = nodes[p].next[ch]
        else:
            nodes[v].link = 0

    return v

def solve():
    n = int(input())

    tree1 = [0, 0]
    tree2 = [0, 0]

    ans = 1

    nodes[0].cnt1 = 1
    nodes[0].cnt2 = 1

    out = []

    for _ in range(n):
        t, v, c = input().split()
        t = int(t)
        v = int(v)

        if t == 1:
            parent_node = tree1[v]
            cur = add_child(parent_node, c)

            tree1.append(cur)

            ans += nodes[cur].cnt2
            nodes[cur].cnt1 += 1

        else:
            parent_node = tree2[v]
            cur = add_child(parent_node, c)

            tree2.append(cur)

            x = cur
            while True:
                ans += nodes[x].cnt1
                nodes[x].cnt2 += 1

                if x == 0:
                    break

                x = nodes[x].link

        out.append(str(ans))

    print("\n".join(out))

solve()

The trie stores all distinct strings that appear as root-to-vertex paths in either tree.

The arrays tree1 and tree2 map original tree vertices to trie nodes. Vertex numbering in the problem starts at 1, so both arrays begin with two elements and ignore index 0.

The root corresponds to the empty string. Initially:

one vertex in tree 1 has empty string,
one path in tree 2 has empty string, namely (1,1).

That is why:

ans = 1
nodes[0].cnt1 = 1
nodes[0].cnt2 = 1

Without this initialization, every answer would be smaller by one.

The add_child function creates trie transitions lazily. If a string already exists, we reuse its node instead of creating duplicates. This is essential because many vertices may share the same string.

The suffix-link construction follows the standard Aho-Corasick logic. Starting from the parent's suffix link, we search for the longest suffix extendable by the new character.

When adding a vertex to tree 1, only one new string appears. We immediately add all matching paths already known in tree 2 through cnt2[cur].

When adding a vertex to tree 2, many new path strings appear, namely all suffixes of the new root string. The loop over suffix links enumerates them exactly once.

The loop intentionally includes node 0. The empty string always corresponds to the path from a vertex to itself in tree 2, so it must participate in counting.

Worked Examples

Sample 1

Input:

Step	Operation	New String	Updated Nodes	Answer
0	initial	`""`	root counts initialized	1
1	add to tree1	`"a"`	cnt1(`a`) += 1	1
2	add to tree2	`"a"`	suffixes: `"a"`, `""`	3
3	add to tree1	`"ab"`	cnt1(`ab`) += 1	3
4	add to tree2	`"b"`	suffixes: `"b"`, `""`	4
5	add to tree2	`"ba"`	suffixes: `"ba"`, `"a"`, `""`	7

The final operation demonstrates why suffix links matter. The string "ba" contributes not only itself but also suffix "a", which matches an existing vertex in tree 1.

Custom Example

Input:

Step	Operation	cnt1(`a`)	cnt2(`a`)	Answer
0	initial	0	0	1
1	tree2 adds `"a"`	0	1	1
2	tree2 adds `"a"` again	0	2	1
3	tree1 adds `"a"`	1	2	3
4	tree1 adds `"a"` again	2	2	5

This trace shows multiplicities. Distinct vertices and distinct paths count separately even if their strings are equal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) amortized	every trie node and suffix-link traversal is processed a constant number of times overall
Space	O(n)	trie nodes, links, and tree mappings

The trie contains at most one node per distinct root-to-vertex string, which is at most the number of operations plus one root node.

An O(n) solution easily fits within the limit for 100000 operations.

Test Cases

# helper: run solution on input string, return output string
import sys
import io

def run(inp: str) -> str:
    input_data = io.StringIO(inp)
    output_data = io.StringIO()

    input = input_data.readline

    class Node:
        __slots__ = ("next", "link", "cnt1", "cnt2")

        def __init__(self):
            self.next = {}
            self.link = 0
            self.cnt1 = 0
            self.cnt2 = 0

    nodes = [Node()]

    def add_child(parent, ch):
        if ch in nodes[parent].next:
            return nodes[parent].next[ch]

        v = len(nodes)
        nodes.append(Node())
        nodes[parent].next[ch] = v

        if parent == 0:
            nodes[v].link = 0
        else:
            p = nodes[parent].link
            while p and ch not in nodes[p].next:
                p = nodes[p].link

            if ch in nodes[p].next:
                nodes[v].link = nodes[p].next[ch]
            else:
                nodes[v].link = 0

        nodes[parent].next[ch] = v
        return v

    n = int(input())

    tree1 = [0, 0]
    tree2 = [0, 0]

    ans = 1

    nodes[0].cnt1 = 1
    nodes[0].cnt2 = 1

    out = []

    for _ in range(n):
        t, v, c = input().split()
        t = int(t)
        v = int(v)

        if t == 1:
            cur = add_child(tree1[v], c)
            tree1.append(cur)

            ans += nodes[cur].cnt2
            nodes[cur].cnt1 += 1

        else:
            cur = add_child(tree2[v], c)
            tree2.append(cur)

            x = cur
            while True:
                ans += nodes[x].cnt1
                nodes[x].cnt2 += 1

                if x == 0:
                    break

                x = nodes[x].link

        out.append(str(ans))

    return "\n".join(out)

# provided sample
assert run(
"""5
1 1 a
2 1 a
1 2 b
2 1 b
2 3 a
"""
) == """1
3
3
4
7"""

# minimum size
assert run(
"""1
1 1 a
"""
) == """1"""

# duplicate strings
assert run(
"""4
2 1 a
2 1 a
1 1 a
1 1 a
"""
) == """1
1
3
5"""

# chain structure
assert run(
"""4
1 1 a
1 2 a
2 1 a
2 2 a
"""
) == """1
1
3
6"""

# sibling paths should not mix
assert run(
"""3
2 1 a
2 1 b
1 1 a
"""
) == """1
1
2"""

Test input	Expected output	What it validates
Single operation	`1`	Correct handling of empty-string base case
Duplicate `"a"` strings	`1 1 3 5`	Multiplicity counting
Deep chain	`1 1 3 6`	Suffix handling on long paths
Sibling branches	`1 1 2`	Only ancestor-descendant paths are valid

Edge Cases

Consider the empty-string case:

1
1 1 a

Initially the empty string already forms one good triple:

(1,1,1)

The algorithm starts with:

ans = 1
cnt1[root] = 1
cnt2[root] = 1

When "a" is inserted into tree 1, cnt2["a"] is zero, so the answer remains 1. This matches the correct behavior.

Now consider repeated identical strings:

After the first two operations:

cnt2["a"] = 2

The third operation inserts one "a" into tree 1, so the algorithm adds 2 to the answer. The fourth operation adds another 2.

The counts represent multiplicities, not distinct strings, which is exactly what the problem asks for.

Finally consider sibling confusion:

Tree 2 contains strings "a" and "b" only. There is no valid path producing "ab" because the corresponding vertices are siblings.

The algorithm never combines unrelated branches because suffix enumeration only follows suffix links of one root-to-vertex string. Every counted string corresponds to a real ancestor-descendant path.