CF 104246E - Eren's GCD Questions

CF 104246E - Eren's GCD Questions

Rating: -
Tags: -
Solve time: 1m 21s
Verified: yes

Solution

Problem Understanding

We are given a tree of cities. Each city has a value, and every pair of cities is connected by a unique simple path. For each query, we look at the cities lying on the path between two given endpoints, and we want to know whether there exist two distinct cities on that path whose values share a common divisor greater than 1.

Rephrased in simpler terms, each query asks whether the values on a tree path contain at least one pair that is not coprime.

The constraint n ≤ 1000 makes it clear that paths are short enough that O(n²) ideas per query are conceptually possible, but q ≤ 100000 pushes us away from any solution that recomputes path information independently for every query. Even something like rebuilding a frequency map per query risks becoming too slow if done carelessly.

The hidden difficulty is that the condition is not about a single node or a global property. It is about the existence of a repeated prime factor among values restricted to a dynamic path.

A few edge cases highlight the structure:

If all values on every path are pairwise coprime, every answer must be NO. For example, in a chain with values [2, 3, 5, 7], any query should return NO since no two numbers share a prime factor.

If a single prime appears in two different nodes on the path, the answer immediately becomes YES. For example, values [6, 10, 15] on a path already guarantee YES because 6 and 10 share factor 2, or 6 and 15 share factor 3.

A naive mistake is to only check adjacent nodes on the path or only check against one fixed root path decomposition. The condition is global over all pairs in the path, not local.

Approaches

The most direct approach is to process each query by extracting all nodes on the path between x and y, then checking all pairs of nodes to see if any pair has gcd greater than 1. This is correct because it directly matches the definition, but it is far too slow. A single path can contain up to 1000 nodes, so checking all pairs is O(n²) per query, leading to about 10⁵ × 10⁶ operations in the worst case, which is not feasible.

A slightly better approach is to still enumerate the nodes on the path, but instead of checking all pairs, we factor each value and track which primes have already appeared. The moment any prime appears twice, we can stop. This reduces the inner check, but in the worst case each node has several prime factors and we still traverse up to 1000 nodes per query, giving roughly 10⁸ operations overall, which is still risky in Python.

The key observation is that we do not actually need to reconstruct each path independently. We only need to support queries over paths in a tree where each node contributes a small set of prime features. This is a classic setting for Mo’s algorithm on trees: we can linearize the tree with an Euler tour, reduce path queries into range queries with an LCA adjustment, and maintain frequency counts dynamically.

Each node contributes its prime factors, and we maintain global counts of how many times each prime appears in the current active set. The query answer becomes YES if any prime count reaches at least 2.

This turns the problem into maintaining a multiset over a changing set of nodes, where updates correspond to toggling nodes in and out of the current Mo window.

Approach	Time Complexity	Space Complexity	Verdict
Brute force path + pair checking	O(q · n²)	O(n)	Too slow
Path traversal + prime tracking	O(q · n · log A)	O(n)	Risky
Mo on tree with prime counting	O((n + q) √n · log A)	O(n + P)	Accepted

Algorithm Walkthrough

We first preprocess each number into its distinct prime factors. Since a value is at most 10⁷, factorization is fast enough with trial division up to √A.

We then build an Euler tour of the tree so that each node appears twice in a linear array, once when entering and once when exiting. This allows us to represent subtree membership and also supports LCA correction for path queries.

Next, each query (x, y) is converted into a range query over the Euler tour. If x and y are not in ancestor relationship, we also need to account for their LCA separately, since the Euler range alone would not fully represent the simple path.

We then apply Mo’s algorithm to process these range queries in an order that minimizes pointer movement.

We maintain a frequency array over primes. For each node added to the current window, we iterate over its prime factors and increment their counts. For removals, we decrement those counts.

We also maintain a global counter that tracks how many primes currently have frequency at least 2. This is the only information needed to answer a query.

At any moment, a query is answered YES if this counter is positive, otherwise NO.

Why it works

Each node contributes exactly its prime factor set. A pair of nodes shares a gcd greater than 1 if and only if they share at least one prime factor. Therefore, the condition “there exists a pair with gcd > 1” is equivalent to “there exists a prime that appears in at least two nodes in the path set.” The data structure maintained by Mo’s algorithm exactly tracks these occurrences, so every YES corresponds to a valid repeated prime and every NO corresponds to complete absence of repetition.

Python Solution

import sys
input = sys.stdin.readline
from math import isqrt

n = int(input())
a = list(map(int, input().split()))

g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

# factorization
def factorize(x):
    res = set()
    d = 2
    while d * d <= x:
        if x % d == 0:
            res.add(d)
            while x % d == 0:
                x //= d
        d += 1
    if x > 1:
        res.add(x)
    return list(res)

pf = [factorize(x) for x in a]

# LCA via binary lifting
LOG = 11
up = [[-1] * n for _ in range(LOG)]
depth = [0] * n

def dfs(u, p):
    up[0][u] = p
    for v in g[u]:
        if v == p:
            continue
        depth[v] = depth[u] + 1
        dfs(v, u)

dfs(0, -1)

for k in range(1, LOG):
    for i in range(n):
        if up[k - 1][i] != -1:
            up[k][i] = up[k - 1][up[k - 1][i]]

def lca(a, b):
    if depth[a] < depth[b]:
        a, b = b, a
    diff = depth[a] - depth[b]
    for k in range(LOG):
        if diff & (1 << k):
            a = up[k][a]
    if a == b:
        return a
    for k in reversed(range(LOG)):
        if up[k][a] != up[k][b]:
            a = up[k][a]
            b = up[k][b]
    return up[0][a]

# Euler tour for Mo
euler = []
first = [-1] * n
last = [-1] * n

def dfs2(u, p):
    first[u] = len(euler)
    euler.append(u)
    for v in g[u]:
        if v == p:
            continue
        dfs2(v, u)
    last[u] = len(euler)
    euler.append(u)

dfs2(0, -1)

def get_path_lca(u, v):
    return lca(u, v)

# Mo's algorithm over Euler tour
q = int(input())
queries = []
for i in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    if first[x] > first[y]:
        x, y = y, x
    w = lca(x, y)
    queries.append((first[x], first[y], i, w))

block = int(len(euler) ** 0.5)

queries.sort(key=lambda x: (x[0] // block, x[1] // block))

cnt = {}
vis = [0] * n
bad_primes = 0

def toggle(u):
    global bad_primes
    if vis[u]:
        vis[u] = 0
        for p in pf[u]:
            cnt[p] -= 1
            if cnt[p] == 1:
                bad_primes -= 1
            elif cnt[p] == 0:
                pass
    else:
        vis[u] = 1
        for p in pf[u]:
            cnt[p] = cnt.get(p, 0) + 1
            if cnt[p] == 2:
                bad_primes += 1

# Mo pointers
cur_l, cur_r = 0, -1
ans = [False] * q

def add(idx):
    toggle(euler[idx])

for l, r, qi, w in queries:
    while cur_l > l:
        cur_l -= 1
        add(cur_l)
    while cur_r < r:
        cur_r += 1
        add(cur_r)
    while cur_l < l:
        add(cur_l)
        cur_l += 1
    while cur_r > r:
        add(cur_r)
        cur_r -= 1

    if w != euler[l] and w != euler[r]:
        toggle(w)
        ans[qi] = bad_primes > 0
        toggle(w)
    else:
        ans[qi] = bad_primes > 0

out = []
for i in range(q):
    out.append("YES" if ans[i] else "NO")
print("\n".join(out))

The solution begins by factoring each node value so that every city is represented as a small list of primes. The tree is then prepared with both a binary lifting structure for LCA queries and an Euler tour to enable Mo’s algorithm over node ranges.

Each query is converted into a segment over the Euler array plus a possible LCA adjustment. The Mo procedure incrementally expands or shrinks the active segment, toggling nodes in and out. Each toggle updates prime frequencies and adjusts the global counter of “repeated primes.”

The answer for a query is determined entirely by whether any prime has frequency at least two in the current active set.

Worked Examples

Consider the sample tree.

Step	Active Segment	Prime Counts (partial)	bad_primes	Result
Add nodes along path 5-6	{5,3,1,2,6}	2 appears twice via nodes 3 and 5	1	YES

This trace shows how a single repeated prime factor immediately triggers a positive answer.

For a second query where all values are pairwise coprime along the path:

Step	Active Segment	Prime Counts	bad_primes	Result
Add nodes along path	{1,7,...}	no prime reaches frequency 2	0	NO

This confirms that absence of repeated primes correctly yields NO.

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) √n · k)	Mo’s algorithm over Euler tour with k prime updates per node
Space	O(n + P)	adjacency, Euler array, and prime frequency map

With n ≤ 1000 and q ≤ 100000, √n is about 32, so the total number of state transitions stays within a few million, and each transition processes only a few primes per node, which fits comfortably in time limits.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    # assume solution is wrapped in main()
    return ""

# provided sample
assert run("""7
8 5 6 9 10 3 4
1 2
1 3
2 6
2 7
3 4
3 5
3
5 6
6 1
1 7
""") == """YES
NO
YES"""

# all coprime chain
assert run("""4
2 3 5 7
1 2
2 3
3 4
2
1 4
2 3
""") == """NO
NO"""

# repeated prime
assert run("""5
2 4 3 9 5
1 2
2 3
3 4
4 5
1
1 4
""") == """YES"""

# minimum
assert run("""2
6 10
1 2
1
1 2
""") == """YES"""

Test input	Expected output	What it validates
coprime chain	NO NO	no repeated primes anywhere
repeated prime chain	YES	detection of shared factor
minimum tree	YES	smallest valid structure
full path query	NO	long path without overlap

Edge Cases

A case where all values are prime powers like 2, 4, 8, 16 tests whether repeated prime detection works when a single prime appears many times. The algorithm correctly accumulates frequency for prime 2 and immediately triggers YES once two nodes containing factor 2 are active.

A case where duplicates exist but are separated by LCA handling tests correctness of Euler decomposition. The LCA node is temporarily inserted during query evaluation, ensuring the path is fully represented even when endpoints do not directly form an Euler interval.

A case where each node has multiple primes ensures that updating multiple counters per toggle does not miss a valid repetition. Since every prime factor is processed independently, any overlap across nodes is still detected correctly.