Caisa and Tree (Codeforces 463E)
Tags: Math, trees

Caisa is now at home and his son has a simple task for him.Given a rooted tree with n vertices, numbered from 1 to n (vertex 1 is the root). Each vertex of the tree has a value. You should answer q queries. Each query is one of the following:  Format of the query is "1 v". Let's write out the sequence of vertices along the path from the root to vertex v: u1, u2, ..., uk (u1 = 1; uk = v). You need to output such a vertex ui that gcd(value of ui, value of v) > 1 and i < k. If there are several possible vertices ui pick the one with maximum value of i. If there is no such vertex output -1.  Format of the query is "2 v w". You must change the value of vertex v to w. You are given all the queries, help Caisa to solve the problem.

Input: The first line contains two space-separated integers n, q (1 ≤ n, q ≤ 105). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2·106), where ai represent the value of node i.Each of the next n - 1 lines contains two integers xi and yi (1 ≤ xi, yi ≤ n; xi ≠ yi), denoting the edge of the tree between vertices xi and yi.Each of the next q lines contains a query in the format that is given above. For each query the following inequalities hold: 1 ≤ v ≤ n and 1 ≤ w ≤ 2·106. Note that: there are no more than 50 queries that changes the value of a vertex.

Output: For each query of the first type output the result of the query.

Note: gcd(x, y) is greatest common divisor of two integers x and y.

Sample Inputs:
4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

Sample Outputs:
-1
1
2
-1
1

Solution (Python):
from sys import stdin, setrecursionlimit
setrecursionlimit(1000000007)
_data = map(int, stdin.read().split())
V = 2100000
(n, q) = (next(_data), next(_data))
a = [next(_data) for _ in range(n)]
g = [[] for _ in range(n)]
for _ in range(n - 1):
    (u, v) = (next(_data) - 1, next(_data) - 1)
    g[u].append(v)
    g[v].append(u)
fss = [[] for _ in range(V)]

def factors(k):
    if fss[k]:
        return fss[k]
    i = 2
    t = []
    v = k
    while i * i <= v:
        if v % i == 0:
            t.append(i)
            while v % i == 0:
                v //= i
        i += 1
    if v != 1:
        t.append(v)
    fss[k] = t
    return t
depth = [0] * n

def init_depth():
    st = [(0, 0, 0)]
    while st:
        (v, p, d) = st.pop()
        depth[v] = d
        for u in g[v]:
            if u != p:
                st.append((u, v, d + 1))
ans = [-2] * n
scope = [[] for _ in range(V)]

def make():
    st = [(0, 0)]
    while st:
        (v, p) = st.pop()
        if v < n:
            st.append((v + n, -1))
            r = (-2, -2)
            for d in factors(a[v]):
                if scope[d]:
                    u = scope[d][-1]
                    r = max(r, (depth[u], u))
                scope[d].append(v)
            ans[v] = r[1]
            for u in g[v]:
                if u != p:
                    st.append((u, v))
        elif v >= n:
            v -= n
            for d in factors(a[v]):
                scope[d].pop()
buf = []
init_depth()
make()
for _ in range(q):
    t = next(_data)
    if t == 1:
        v = next(_data) - 1
        buf.append(ans[v] + 1)
    elif t == 2:
        v = next(_data) - 1
        x = next(_data)
        a[v] = x
        make()
    else:
        assert False
print('\n'.join(map(str, buf)))

Solution (Python):
from functools import lru_cache
MAXA = 2 * 10 ** 6
spf = [0] * (MAXA + 1)
for i in range(2, MAXA + 1):
    if spf[i] == 0:
        spf[i] = i
        for j in range(i * i, MAXA + 1, i):
            if not spf[j]:
                spf[j] = i

def get_prime_factors2(a):
    last_p = -1
    while a != 1:
        if spf[a] != last_p:
            yield spf[a]
        last_p = spf[a]
        a //= spf[a]

@lru_cache(maxsize=None)
def get_prime_factors(a):
    return tuple(get_prime_factors2(a))
has_p = [[] for i in range(MAXA + 1)]

def dfs(c_queries, ans):
    s = [1]
    true_s = []
    vis = [0] * (n + 1)
    while s:
        c = s[-1]
        if not vis[c]:
            true_s.append(c)
            vis[c] = 1
            if c_queries[c]:
                max_u = (-1, -1)
                for p in get_prime_factors(a[c]):
                    if has_p[p]:
                        max_u = max(max_u, has_p[p][-1])
                for q_i in c_queries[c]:
                    ans[q_i] = max_u[1]
            depth = len(true_s)
            for p in get_prime_factors(a[c]):
                has_p[p].append((depth, c))
            for ne in adj[c]:
                s.append(ne)
        else:
            if true_s and c == true_s[-1]:
                for p in get_prime_factors(a[c]):
                    has_p[p].pop()
                true_s.pop()
            s.pop()

def solve(i, j, ans):
    c_queries = [[] for i in range(n + 1)]
    for (q_i, (_, v)) in enumerate(queries[i:j + 1], len(ans)):
        c_queries[v].append(q_i)
    ans.extend([0] * (j - i + 1))
    dfs(c_queries, ans)
if __name__ == '__main__':
    (n, q) = map(int, input().split())
    a = [None] + list(map(int, input().split()))
    adj = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (x, y) = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)
    queries = []
    for i in range(q):
        queries.append(list(map(int, input().split())))
    ans = []
    i = 0
    j = 0
    while i < q:
        while j + 1 < q and queries[j + 1][0] == queries[j][0]:
            j += 1
        if queries[i][0] == 1:
            solve(i, j, ans)
        else:
            for k in range(i, j + 1):
                a[queries[k][1]] = queries[k][2]
        (i, j) = (j + 1, j + 1)
    print(*ans, sep='\n')

Solution (Python):
MAXA = 2 * 10 ** 6
spf = [0] * (MAXA + 1)
for i in range(2, MAXA + 1):
    if spf[i] == 0:
        spf[i] = i
        for j in range(i * i, MAXA + 1, i):
            if not spf[j]:
                spf[j] = i
prime_factors = [None] * (MAXA + 1)

def get_prime_factors2(a):
    last_p = -1
    while a != 1:
        if spf[a] != last_p:
            yield spf[a]
        last_p = spf[a]
        a //= spf[a]

def get_prime_factors(a):
    if not prime_factors[a]:
        prime_factors[a] = tuple(get_prime_factors2(a))
    return prime_factors[a]
has_p = [[] for i in range(MAXA + 1)]

def dfs(c_queries, ans):
    s = [1]
    true_s = []
    vis = [0] * (n + 1)
    while s:
        c = s[-1]
        if not vis[c]:
            true_s.append(c)
            vis[c] = 1
            if c_queries[c]:
                max_u = (-1, -1)
                for p in get_prime_factors(a[c]):
                    if has_p[p]:
                        max_u = max(max_u, has_p[p][-1])
                for q_i in c_queries[c]:
                    ans[q_i] = max_u[1]
            depth = len(true_s)
            for p in get_prime_factors(a[c]):
                has_p[p].append((depth, c))
            for ne in adj[c]:
                s.append(ne)
        else:
            if true_s and c == true_s[-1]:
                for p in get_prime_factors(a[c]):
                    has_p[p].pop()
                true_s.pop()
            s.pop()

def solve(i, j, ans):
    c_queries = [[] for i in range(n + 1)]
    for (q_i, (_, v)) in enumerate(queries[i:j + 1], len(ans)):
        c_queries[v].append(q_i)
    ans.extend([0] * (j - i + 1))
    dfs(c_queries, ans)
if __name__ == '__main__':
    (n, q) = map(int, input().split())
    a = [None] + list(map(int, input().split()))
    adj = [[] for i in range(n + 1)]
    for i in range(n - 1):
        (x, y) = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)
    queries = []
    for i in range(q):
        queries.append(list(map(int, input().split())))
    ans = []
    i = 0
    j = 0
    while i < q:
        while j + 1 < q and queries[j + 1][0] == queries[j][0]:
            j += 1
        if queries[i][0] == 1:
            solve(i, j, ans)
        else:
            for k in range(i, j + 1):
                a[queries[k][1]] = queries[k][2]
        (i, j) = (j + 1, j + 1)
    print(*ans, sep='\n')