Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya…

  1. User

    Ilya is very fond of graphs, especially trees. During his last trip to the forest Ilya found a very interesting tree rooted at vertex 1. There is an integer number written on each vertex of the tree; the number written on vertex i is equal to ai.

    Ilya believes that the beauty of the vertex x is the greatest common divisor of all numbers written on the vertices on the path from the root to x, including this vertex itself. In addition, Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have.

    For each vertex the answer must be considered independently.

    The beauty of the root equals to number written on it. Input

    First line contains one integer number n — the number of vertices in tree (1 ≤ n ≤ 2·105).

    Next line contains n integer numbers ai (1 ≤ i ≤ n, 1 ≤ ai ≤ 2·105).

    Each of next n - 1 lines contains two integer numbers x and y (1 ≤ x, y ≤ n, x ≠ y), which means that there is an edge (x, y) in the tree.

    Output

    Output n numbers separated by spaces, where i-th number equals to maximum possible beauty of vertex i.

    Examples

    Input

    2 6 2 1 2

    Output

    6 6

    Input

    3 6 2 3 1 2 1 3

    Output

    6 6 6

    Input

    1 10

    Output

    10

  2. DeepSeek Assistant

    We need to solve problem: tree rooted at 1, each vertex i has integer a_i. Beauty of vertex x is gcd of all numbers on path from root to x (including x). Additionally, we can change the number in exactly one arbitrary vertex (any vertex, not necessarily on the path) to 0 or leave all unchanged. The change is applied globally? The problem says: "Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have." This is typical problem "GCD on a tree with one zero allowed". For each vertex x, we can choose to set some vertex (anywhere) to 0, and then compute beauty (gcd of path from root to x). The beauty is the gcd of values along the path, possibly with one value set to 0 (which is effectively removing that vertex's contribution because gcd(a,0)=a). Actually, gcd(a,0) = |a|, but we consider positive integers; typically gcd(x,0)=x. So setting a vertex's value to 0 effectively removes that vertex from the gcd calculation, i.e., we can ignore its value. However, careful: if we set a vertex's value to 0, then the gcd of the whole path will be gcd of all other values, because gcd(0, rest) = rest. But note: if we set a vertex on the path to 0, its contribution is removed. If we set a vertex not on the path to 0, it doesn't affect the beauty at x. So effectively, for each vertex x, we can choose to ignore (remove) at most one vertex's value from the path from root to x (by setting it to 0) OR we can choose to ignore a vertex not on the path (which does nothing). So the maximum beauty is the gcd of all values on path, OR the gcd of the path after removing one element (any one), i.e., we can skip one element. But careful: we are allowed to set any vertex in the whole tree to 0, but only one vertex globally. However, the question: "Now for each vertex Ilya wants to know the maximum possible beauty it can have." For each vertex independently, we consider we can make a choice of which vertex to set to 0 (or none) that maximizes that vertex's beauty. This is typical interpretation: we consider the scenario where we can change exactly one vertex to 0 (or none), and we want for each vertex x the best possible beauty for x, assuming we can choose which vertex to set to 0 in a way that benefits x, without regard to other vertices (since they are considered independently). So effectively, for each x we can choose to ignore any one vertex (or none) in the whole tree, but only one globally. But if we consider each vertex independently, it's like we can choose a different vertex to set to 0 for each x? The problem statement: "Ilya can change the number in one arbitrary vertex to 0 or leave all vertices unchanged. Now for each vertex Ilya wants to know the maximum possible beauty it can have." This suggests that for each vertex independently, we can decide to set some vertex to 0 to maximize beauty of that vertex. Typically, in such problems, it's allowed to pick different vertex to zero for each query, because it's just an independent hypothetical scenario. So yes, for each vertex x we can choose a different vertex to set to 0. So the answer for each x is max over choices of a vertex v to set to 0 (or none) of the beauty at x (i.e., gcd of path values with possibly v's value replaced by 0). Since setting v not on path does nothing, the best is either not set any or set some vertex on the path to 0. So answer is max( gcd of all values on path, max_{v on path from root to x} ( gcd of all values on path except v ) ). But careful: if we set v to 0, the path gcd becomes gcd of all a_i for i on path, i != v. However, if v is the root? root is also on path. So yes.

    So we need for each node x: compute g_x = gcd of all a_i along root->x. Also we need to consider for each x, the best possible after removing one vertex. That is essentially the maximum possible gcd among: g_x (no removal), and for each position v in path, compute gcd of path without that vertex. However computing that naively per node is O(depth^2) worst-case.

    We need to compute for each node x, the maximum beauty.

    Observation: The beauty with one removal is essentially the maximum over choices: either keep as is, or remove exactly one element. And note that gcd of a set S of numbers, and we want to compute the maximum possible gcd after removing at most one element, we can compute the gcd of all numbers except one; but we want the maximum possible gcd among all choices of which to remove. That maximum gcd is either the gcd of the whole set, or maybe larger if removing a number that doesn't divide the gcd.

    Specifically, for a multiset of numbers, define f(S) = max_{x in S} gcd(S \ {x}) (or also possibly not removing any gives gcd(S)). This can be computed if we know the gcd of the whole set and also the gcd of the set after removing each element, but we need efficient.

    For each node x, the set S = values on path from root to x. Let g = gcd(S). If we remove a vertex v, the gcd becomes gcd( gcd of prefix up to before v, gcd of suffix after v ). Essentially, if we denote prefix gcd from root to node i as pref[i] = gcd(a_1, ..., a_i along path) and suffix? Since path is linear, we can compute for each position i in path, the gcd of all except i as gcd(prefix_gcd up to parent of i, suffix_gcd from child onward). But suffix_gcd is not constant for entire path because the order is from root to leaf. However, for a given node x, its path is fixed. So we can compute for each ancestor y (including x) of x, the gcd of all values on path except y, by computing prefix gcd up to y's parent and suffix gcd from y's child down to x. But careful: If y is the node x itself, then suffix after y is empty, so gcd except y is just prefix up to parent. If y is root (node 1), then prefix is empty, so gcd except root is suffix from child (node after root) down to x.

    Thus, for each node x, we need to compute for all ancestors y of x (including x), the value h(y,x) = gcd( pref_gcd up to parent(y), suff_gcd from child(y) to x). Then answer for x is max(g_x, max_{y in ancestors} h(y,x)). But doing that per node by iterating ancestors would be O(n^2) in worst case (chain). Need smarter.

    Observation: The answer for node x is essentially the maximum possible gcd that can be obtained by removing at most one element from the path. This is like we can consider the gcd of the entire path and maybe some larger gcd if we remove a "bad" element that prevents a higher gcd.

    We can think about the possible gcd values. Since a_i up to 2e5, we can perhaps use divisor-based DP. Many solutions to this problem (CF 1101D? Actually it's "GCD on a tree" with one zero, CF round #555 (Div. 3) maybe? I recall problem "GCD on a tree with one zero" from Codeforces 1101D? Let's think: There is a known problem: "GCD on a tree" where you can change one vertex to zero, answer for each node. It's Codeforces Round #1101 (Div. 2) problem D? Actually, 1101D is "GCD Counting" about longest path where gcd > 1. Not that.

    Maybe I've seen this problem: "GCD on a Tree" where you can set one vertex to zero, I think it's Codeforces 274B? Not sure. Let's search memory: Problem "GCD on a Tree" from CF Round # ??? Actually I recall a problem: "GCD on a Tree" from Codeforces Round # 112 (Div. 2) maybe. But more concretely, the solution involves precomputing gcd prefixes and storing for each node some set of possible gcds after removing one element from the path up to that node. There is a known approach: For each node, we compute the following: ans[node] = max( ans[parent]? Actually we need per node answer.

    Wait, we can think about DP from root to leaves, maintaining some data structures that allow us to compute the maximum possible beauty for each node efficiently. Since we can remove at most one vertex anywhere on the path, the result for node x is maximum of:

    • gcd of all values on path (call it g[x])
    • gcd of all values on path after removing some vertex y. That can be expressed as: let the path be v0=1, v1,..., vk = x. Then for each i, the gcd after removing vi is gcd( prefix_gcd[i-1], suffix_gcd[i+1] ). But suffix_gcd[i+1] can be computed as gcd of values from vi+1 to vk.

    If we precompute for each node its value a_i, and we can compute prefix gcd along the path as we DFS: pref[node] = gcd(pref[parent], a[node]). However, we need to compute the maximum after removal without iterating all ancestors.

    We can compute for each node the set of possible gcd values that can be obtained by taking the gcd of some suffix of the path? Not exactly.

    Alternatively, we can compute the answer for each node using the concept: For each divisor d, we can find the deepest node where something holds. But maybe easier: We can do two DFSes: one to compute prefix gcds and also maintain for each node a map of gcds that occur on the path when we skip exactly one element. Actually, we can compute for each node a set of gcd values that can be obtained by removing exactly one vertex from the path to that node. Then the answer for node is the max in that set, and also include the full path gcd. But if we store sets for each node, merging from parent? However, the path is linear, we could propagate sets. But the size of such sets might be large (up to number of distinct gcd values). However, note that the number of distinct prefix gcds along a path is O(log max a) because each time gcd changes it divides the previous value. Similarly, suffix gcds. So the number of distinct gcds for a path is O(log maxA). So we can store a small set of candidate gcds.

    We need to compute, for each node, the maximum possible gcd after removal. This can be done by considering two cases: removing some vertex in the prefix part before the current node, or removing the current node itself? Actually, we need to consider removal of any vertex on path.

    Idea: For each node, we can compute the answer using the following DP:

    Let dp1[node] = gcd of all values from root to node (i.e., pref[node]). Now, consider we are allowed to change one vertex to 0. We want the best beauty at node.

    We can compute an array best[node] = maximum beauty possible at node.

    We can compute best[node] by considering two possibilities:

    1. We did not change any vertex, or we changed some vertex on the path before node? Actually the change can be done anywhere, but only one change globally. So for a given node, the best we can do may involve changing a vertex that is not necessarily on the path? That's irrelevant. So best[node] = max( dp1[node], some other value from removal).

    Now, how to compute the maximum after removal? For node, we need the maximum of gcd of all path except some ancestor (including itself). This can be computed as: let g = dp1[node]. But removal can yield a higher gcd only if there is a number that is not a multiple of the higher gcd? Actually, we can think of computing for each node the gcd of the path with one element omitted. That can be larger than dp1[node].

    Observation: For a set of numbers, the gcd after removing one element is either equal to the gcd of the whole set, or it's the gcd of the set of numbers that are all multiples of some larger divisor. In other words, if we want to achieve a gcd value d > dp1[node], then all numbers on the path except at most one must be divisible by d. Because if we remove the element that is not divisible by d, then the remaining ones are all divisible by d, so gcd is at least d. Actually, for gcd to be exactly d, we need all remaining numbers to be divisible by d, and at least one number's gcd after removal could be multiple of d, but we are looking for maximum possible d, so we can consider each divisor.

    Therefore, we can reframe: For each node x, answer is max d such that on the path from root to x, at most one vertex has a value not divisible by d. Because if we set that vertex to 0 (or if it's not divisible by d, we can remove it by zeroing), then all other numbers are divisible by d, so the gcd after zeroing that vertex is at least d; it might be larger than d, but if it's larger, then d is not maximum. But we are seeking maximum beauty, which is the largest d that can be achieved. So answer is max d such that the number of vertices on the path with a_i not divisible by d is at most 1.

    Because if there is at most one such vertex, we can zero it (if it's on the path; if it's not, we don't care). But if there is 0 such vertices, then d divides all, and beauty (without zeroing) is at least d, but we can also get larger d maybe. So the answer is the maximum d for which count of non-divisible on path <= 1.

    Now this formulation is nice: For each node, we need to find the maximum d such that the number of vertices on its root path whose a_i is not divisible by d is at most 1. And d is a divisor of some a_i? Actually, d can be any integer, but the maximum possible beauty is always a divisor of some a_i? Since beauty is gcd of some subset of a_i values, it must divide each element in that subset; thus it must divide at least one element? Actually, if we zero a vertex, the remaining numbers' gcd will divide each of those numbers. So beauty will be a divisor of all numbers except possibly the zeroed one? But after zeroing, we take gcd of numbers which are all positive; the gcd is a divisor of each of those numbers. So beauty is a divisor of each of the remaining numbers, and thus a divisor of at least one number? It will be a divisor of all remaining numbers. So it must be a divisor of the gcd of those numbers. The gcd is a divisor of each number. So beauty is a divisor of all numbers in the set (except possibly the zeroed one). So beauty will be a divisor of the numbers that are not zeroed. But if we set a vertex to 0, its value is ignored. So beauty must be a divisor of every other number on the path. Therefore, beauty must divide all numbers except possibly one. Thus, the maximum d must be a divisor of all numbers on the path except at most one. And d could be any number; but the maximum will be a divisor of many numbers. Since a_i <= 2e5, we can use divisor enumeration.

    Thus, for each node, we need to find the largest d such that at most one vertex on the path has a_i not divisible by d.

    We can precompute for each divisor d, the list of nodes where a_i is not divisible by d? Or we can process the tree with DFS and maintain for each divisor d a count of how many vertices on current path are not divisible by d. Then, as we traverse, we can update these counts. Since a_i <= 2e5, the number of divisors of a_i is at most about 128? Actually max divisor count for numbers up to 200k is around 128? Let's check: 166320 has 128 divisors? The max for 200k might be around 160 maybe. For 2e5, the max divisor count is something like 128? Actually 180180 has 128 divisors, but that's above 200k? 166320 has 128, 196560? I'd approximate around 128-160. But worst-case could be around 240? The maximum number of divisors for numbers up to 2e5 is maybe 160. So each a_i has O(sqrt(a_i)) divisors, but we can precompute all divisors. So we could maintain an array cnt[d] = number of vertices on current DFS path whose value is not divisible by d. Then at node x, we want to find the maximum d such that cnt[d] <= 1. However, cnt[d] is path-specific: as we go down, we update for each divisor d of a_i? Wait, we need for each d, count of vertices on path that are NOT divisible by d. That's the number of "bad" vertices for d. When we visit a node, for each divisor d of a_i? Actually, we need to update cnt for all d? But we cannot iterate over all d up to 2e5 for each node (2e5 * 2e5). Instead, we need to only care about d that could be answer? But we need to compute answer = max d with cnt[d] <= 1. That is like we need to maintain an array of cnt[d] for all d, but we can update only those d that are affected by the node's value. But what about d that are not divisors of a_i? For a given d, whether a_i is divisible by d determines if it contributes to cnt[d]. When we add a node, for each d, we need to increment cnt[d] if a_i % d != 0. That's again too many. So we need smarter approach.

    We can reverse the viewpoint: Instead of iterating over d, we can consider for each node the possible d values that could be answer, i.e., d divides a lot of numbers. Since a_i up to 2e5, we can use sieve-like enumeration: For each possible d, we can compute the depth at which it fails (i.e., more than one non-divisible). But we need per node answers.

    Alternatively, consider classic solution: Do a DFS, maintain for each node a set of pairs (gcd, count) representing the gcd of a suffix after removing one element? Actually, many solutions for this problem (I recall) use two DFSes: one to compute prefix gcds, and one to compute something like "alternative gcd" that allows skipping one node. Let's try to derive.

    Let pref[u] = gcd from root to u. Now, for each node u, we also want to consider the possibility of removing a node on its path. That can be expressed as: we can take the gcd of pref values with one skip.

    If we consider the path as sequence, we can compute for each node u the answer as max( pref[u], best_skip[u] ), where best_skip[u] is the maximum gcd we can get by removing exactly one vertex on the path.

    We can compute best_skip[u] by combining information from parent. Suppose we have for parent p, we know some candidate gcds that can be achieved by removing a vertex on the path to p. Then for node u, we can extend those.

    Specifically, when moving from parent p to child u, the new node adds a value a_u. The set of possible gcds after one removal to reach u can be derived from two scenarios:

    • We already used the zero change before reaching u (i.e., we changed some vertex in the path to p to 0). Then for u, we cannot change another vertex. So the gcd we get is gcd( previous_gcd_with_one_removal, a_u ). Because we already removed one vertex earlier; now we must include a_u as is. So from each candidate gcd from parent (representing gcd of path to p with one removal already applied), we can update candidate for u as gcd(candidate, a_u). Also note that we could also choose not to have used the change yet, meaning we still have the ability to change a vertex (maybe u or some earlier) to 0. So we need to consider cases where we have not used the change yet, but we might use it later.

    Thus we can maintain for each node two sets:

    • dp0[u]: the set of possible gcd values for the path from root to u without using any change (i.e., the gcd of the whole path). Actually there's just one value: pref[u]. But we can also consider multiple? Actually gcd of whole path is deterministic.
    • dp1[u]: the set of possible gcd values for the path from root to u after using exactly one change (i.e., we have set some vertex on the path to 0). And we also need to consider the state where we haven't used the change yet? But we want maximum beauty at node u, which allows at most one change. So we need to consider the scenario where we have used the change already, and also the scenario where we haven't used it yet (so we may use it later, but at node u we haven't used it, so the beauty is the gcd of all values so far). But if we haven't used the change yet, then the beauty at u is just pref[u]. That's already considered.

    But we also need to consider using the change at u itself (i.e., setting a_u to 0). That would give beauty = pref of parent (since we ignore u). So that's also a candidate.

    Thus, we can compute for each node u:

    • ans[u] = max( pref[u], max over dp1[u] ) where dp1[u] are gcd values after using exactly one change.

    We need to compute dp1[u] efficiently. Since number of distinct gcd values along a path is O(log A) (since each time gcd changes, it divides previous), the set dp1[u] size can also be bounded O(log A) maybe. Actually, dp1[u] can be derived from parent's dp0 and dp1. Let's define:

    Let g0[u] = pref[u] (gcd of all values on path, no changes).

    We also define maybe two states:

    • state A: we have not used any change yet (i.e., we are considering the full path up to now). This state's value is g0[u].
    • state B: we have used exactly one change somewhere on the path. The gcd value after that change we denote as cur.

    When we go from parent p to child u, we transition:

    From state A (no change used yet) at p, which has value g0[p]:

    • If we do not use change at u: we go to state A at u with value gcd(g0[p], a_u) = g0[u].
    • If we use change at u (set a_u to 0): then we use the change now, and after that, the gcd becomes g0[p] (since we ignore u). So this leads to state B at u with value g0[p].
    • Also, we could use change earlier? But state A hasn't used change, so using change earlier would be state B at p. So that's separate.

    From state B at p, which has some value val (gcd of path up to p with one change already used):

    • We cannot use another change, so we must include a_u as is. So state B at u gets gcd(val, a_u).

    Thus, dp1[u] (the set of values in state B at u) can be derived by:

    • Taking each value in dp1[p] and gcd with a_u.
    • Additionally, if we consider using the change at u (coming from state A at p), we add g0[p] (since that's the gcd after ignoring a_u). Also, note that state B values could also come from other ways? That's it.

    Thus, if we maintain for each node the set of possible gcd values after exactly one change (i.e., state B), we can compute for children. The size of this set could increase if we keep adding many distinct gcd values, but note that gcd operation reduces values. Since each time we take gcd with a_u, the number of distinct values remains limited. Actually, dp1[p] is a set of numbers; after gcd with a_u, many may collapse. So total distinct values per node is O(log A) because each value is a divisor of some prefix? More precisely, the number of distinct gcd values from prefixes is O(log A). For dp1, we also have values from g0 of ancestors (by removing later nodes) possibly. But maybe the total distinct values along a path is still O(log A). Let's test: Suppose we have a path of length n. For each node, g0 is a decreasing (in terms of divisibility) sequence; g0 values only change O(log A) times. Similarly, dp1 values might be like gcd of some subset after removal. Could the number be larger? Consider: at each step, we take previous set (dp1) and gcd with a_u, then also add g0[parent]. So set size can grow but bounded by the number of distinct gcd values encountered. There is known result: the number of distinct prefix gcd values is O(log max value). Actually, it's O(log max value) because each time gcd changes, it at least halves? Not exactly halves, but gcd reduces by at least factor 2 when it changes? For two numbers, gcd(a,b) <= min(a,b). But the number of distinct values when repeatedly taking gcd with new numbers is limited: it's the number of divisors of the final gcd? Not exactly. Let's analyze: Starting from g0[1]=a1. Then for each new a_i, g0[i] = gcd(g0[i-1], a_i). So g0[i] is always a divisor of g0[i-1]. So the sequence of g0[i] is a chain of divisors. The number of divisors of a number up to 2e5 is at most around 160. So g0[i] can change at most 160 times? Actually, each time g0[i] is a divisor of previous. The total number of distinct values across the whole path is bounded by the number of divisors of a1? But a1 is up to 2e5, so at most ~160. That's true because g0[i] divides a1. Similarly, g0[i] also divides each a_i, but a1 may have many divisors. However, note that a1 could be something like 1, which has only 1 divisor. But in general, the maximum number of distinct prefix gcd values along any path is bounded by the maximum number of divisors of any number up to 2e5, which is about 160. That's a small constant. Similarly, dp1 values are gcd of some subset, but they will also divide a1? Not necessarily. For example, if we remove root's value, then the gcd might be something that doesn't divide a1? But the gcd of numbers from nodes after root, which may not divide a1. However, consider that the set of numbers considered are a subset of the a_i's on the path. Their gcd is some divisor of each number in that subset, but not necessarily of a1. But it will be a divisor of some other node's a_j. However, the number of possible distinct gcd values that can appear from any subset of numbers on a path might still be limited? Could be larger than 160? Possibly, but maybe still O(sqrt(maxA))? Let's think: each a_i up to 2e5, the number of distinct gcd values from any combination of these numbers is bounded by the number of divisors of any a_i? Actually, if we take a set of numbers, their gcd must be a divisor of each, so it must be a common divisor of the set. The gcd value must be a divisor of the first number. So if we fix the first number (say the root's a1), any gcd derived from a subset that includes the root (if we haven't removed root) must divide a1. But if we remove root, then we start from child. So the gcd after removal of root could be something that does not divide a1? But it must divide the second node's value, and so on. So any gcd value we get from a subset of the path will divide at least one of the numbers on the path. However, there could be many possible divisors across different numbers. The total number of distinct divisors across all numbers up to 2e5 is bounded by sum of divisor counts of each number, which could be O(n log max) if we sum over all numbers? Actually, sum_{i=1}^{n} d(a_i) where each d(a_i) ≤ 160, so total is at most 160n, which is too large to store per node. But the distinct gcd values we encounter along a specific path may be limited. Because at each step, we only generate new values by gcd-ing with a new number or using g0[parent]. The number of distinct gcd results when repeatedly taking gcd with a sequence is O(log A) per step? There's known fact: For a fixed starting set, the number of distinct gcds you can get by taking gcd with a sequence is O(log A). Actually, there's a typical solution for "GCD on a tree" problems where they store a map of gcd -> frequency, and the size of map is O(log max). Let's analyze: Suppose we have a set of numbers. We maintain a map of gcd values that can be obtained from a path with one skip. Many CF solutions use exactly this: For each node, they maintain a map of possible gcd values after using zero or one skip, and they combine with child. The map size is small because each time we take gcd with a new number, the number of distinct gcd results is bounded by the number of divisors of that number? Actually, consider we have a list of candidate values (say some integers). When we compute gcd(candidate, a_u) for each candidate, the resulting set size is at most the number of candidates. So if we start with a set of size K, after gcd with a_u we get at most K distinct results. Additionally, we add a new candidate g0[parent] (from skipping current). So total size could increase by 1 each step. If we do this for n=2e5 steps, the size could become O(n) in worst-case if each step adds a new distinct value. But is that possible? The added candidate is g0[parent], which is a prefix gcd. The number of distinct prefix gcd values along the path is limited (as argued, O(divisors of a1) which is at most 160). So that's bounded. For the other part, the set derived from previous dp1 values (by gcd with a_u) could potentially be many distinct values? Let's simulate: dp1[p] is a set of numbers. Could its size become large? Consider that dp1 values are derived from combinations of skipping different nodes. They are essentially gcds of various suffixes after removing one element. Could there be many distinct such gcds? Let's think: For a path of length L, there are L possible gcds after removing each element. However, many may be equal. But worst-case could there be L distinct values? Let's try to construct: Suppose a_i are distinct primes? But if a_i are primes, gcd of any subset of size >1 is 1, so all removed gcds are 1 except maybe when removing all but one? Actually, if we have a path of primes: say 2,3,5,7,... The full path gcd is 1. If we remove one element, the gcd of the rest is also 1 (since at least two primes remain). So all are 1. Not many distinct.

    To get many distinct gcd values, we need the gcd to vary as we remove different elements. Suppose numbers are arranged so that gcd of all but i is some distinct value. For instance, if we have numbers that are multiples of various combinations. But gcd of many numbers tends to be small. For a set of numbers, the gcd of all but i is equal to gcd( all numbers ) if the removed number is not the only one not divisible by some factor; else it might be larger. Could we have O(L) distinct values? Possibly if each removal gives a different gcd. Let's attempt: Let the numbers be: a1 = product of many primes, a2 = product of a subset, etc. But gcd values are divisors of the overall product. The number of distinct divisors of a number up to 2e5 is at most 160. So if all a_i are within 2e5, then any gcd of any subset of them is also a divisor of each number in the subset, and in particular, it divides the first number in the subset. But the gcd values across different subsets could be many if they are divisors of different numbers. However, since each a_i is bounded by 2e5, the total number of distinct integers that can appear as a divisor of some a_i is at most sum of divisor counts, which is large, but along a specific path, we might get many different divisors from different a_i. Could we have e.g., 1000 distinct gcd values? The total number of distinct divisors across all numbers up to 2e5 is about 2e5 * (divisor density) ~ 2e5 * log log 2e5 maybe 1e6? But for a single path of length up to 2e5, we could have many distinct a_i each with many divisors. But the gcd operation reduces to common divisors. The gcd of a set is a divisor of each element, so it must be a common divisor of all elements in the set. The set is the whole path except one. So for each candidate removal, the gcd is a divisor of the gcd of all elements except that one. Could that produce many distinct values? Possibly if the numbers are chosen such that the common divisor of all but each i yields different divisors. For each i, the set is all numbers except a_i. The gcd of that set is the gcd of all numbers with a_i possibly excluded. This could vary. Example: Suppose we have numbers: 2, 3, 6. Full set {2,3,6} gcd=1. Remove 2 -> {3,6} gcd=3. Remove 3 -> {2,6} gcd=2. Remove 6 -> {2,3} gcd=1. So we get {1,2,3}. That's 3 distinct values for L=3. For L=4, can we get 4 distinct? Let's try: a1=2, a2=3, a3=5, a4=30. Full gcd=1. Remove 2 -> gcd(3,5,30)=1? gcd(3,5)=1 => gcd(1,30)=1. Remove 3 -> gcd(2,5,30)=1? 2 and 5 gcd=1. Remove 5 -> gcd(2,3,30)=1? 2 and3 gcd=1. Remove 30 -> gcd(2,3,5)=1. So only 1. Not many.

    Better: Use numbers that are all multiples of some base but each missing one prime factor. For example, let p1,p2,...,pk be distinct primes. Let the numbers be: for each i, the product of all primes except pi. Then the gcd of all numbers except one? Let's see: For n numbers, each number is missing a different prime. The gcd of all numbers is 1 (since for any prime pi, the number missing pi is present in all others? Actually, if we have numbers: N1 = product of all primes except p1, N2 = product except p2, ..., Nk = product except pk. Then the gcd of all numbers is 1 because for each prime pi, there is at least one number (Ni) that does not contain pi? Actually, Ni contains all primes except pi, so it contains pj for j != i. So for prime pi, the number Ni does not contain pi, but all other numbers Nj (j != i) do contain pi. So for prime pi, among all numbers, there is exactly one (Ni) missing pi, but the others contain pi. So the gcd of all numbers: take a prime pi. Is pi dividing all numbers? It divides all except Ni, so it does not divide all numbers. Hence pi is not in gcd. So gcd=1. Now, if we remove Ni (the one missing pi), then the remaining numbers are all that contain pi? Actually, after removing Ni, the set includes all numbers except Ni. For prime pi, all remaining numbers contain pi? Let's check: For pi, numbers Nj for j != i contain pi because they are product of all primes except pj, which includes pi if j != i. So yes, after removal of Ni, all remaining numbers contain pi. So the gcd of the set after removing Ni includes pi. Moreover, for any other prime pj (j != i), does it divide all remaining numbers? For pj, the number Nj is missing pj, but Nj is still present if we removed Ni and i != j. So pj does not divide Nj. So pj does not divide all remaining numbers. Thus the gcd after removing Ni is exactly pi? Actually, we need to compute gcd of numbers: N1 (if i=1, we remove N1) then remaining are N2,...,Nk. What is gcd of N2,...,Nk? For prime pi (i=1), all contain pi. For any other prime pj (j>1), the number Nj is missing pj, so that prime is not in all. Thus the gcd is exactly pi? But is it exactly pi? N2 = product of all primes except p2. That includes p1 (pi) and p3,...,pk. N3 includes p1, etc. So all contain p1. So gcd at least p1. Could there be a product of p1 with others? No, because p2 is missing from N2, so p2 is not common. So the gcd is p1. So after removing Ni, gcd = pi. So we get distinct primes for each removal. For n numbers, we get n distinct gcd values (the primes). But note that our numbers are product of (k-1) primes; the magnitude of these numbers grows exponentially with k. Since a_i <= 2e5, we can only have a limited number of primes such that product of all but one <= 2e5. Let's see: the product of first m primes: 23=6, 5=30, 7=210, 11=2310, 13=30030, 17=510510 > 200k. So up to prime 13, product is 30030, 17 gives 510510 > 200k. So the maximum number of primes we can have such that product of (m-1) primes <= 200k? For m=6: primes 2,3,5,7,11,13 product of any 5 of them? Product of first 6 primes: 23571113 = 30030? Actually 23=6, 5=30, 7=210, 11=2310, 13=30030. So product of first 6 primes is 30030. So product of any 5 of them is <= 30030 as well, but we need each a_i <= 200k, so that's fine. For m=7: product of first 7 primes: 2357111317 = 510510, product of 6 of them (excluding the largest 17) is 30030, which is still <=200k. Excluding 13: product 23571117 = 39270? Let's compute: 23=6, 5=30, 7=210, 11=2310, 17=39270. That's ok. Excluding 11: 23571317 = 46410? 23=65=307=21013=273017=46410. Ok. Excluding 7: 235111317 = 23=65=3011=33013=429017=72930. Excluding 5: 237111317 = 23=67=4211=46213=600617=102102. Excluding 3: 257111317 = 25=107=7011=77013=1001017=170170. Excluding 2: 357111317 = 35=157=10511=115513=15015*17=255255 >200k. So some combinations exceed 200k. So we can have at most maybe 6 numbers? Let's see we need each a_i <= 200k. So we could have up to maybe 7 numbers? For m=7, product of all 7 is 510510, but we only need each a_i = product of 6 primes (excluding one). Among the 7 numbers, some will be product of the 6 smallest primes, which is 30030 (excluding the largest 17) - that's fine. The one excluding 13 is 39270, fine. Excluding 11 is 46410, fine. Excluding 7 is 72930, fine. Excluding 5 is 102102, fine. Excluding 3 is 170170, fine. Excluding 2 is 255255 >200k (exceeds). So for m=7, the number a_i that excludes 2 would be 255255 >200k, so that's invalid. So we could have at most 6 numbers if we require all a_i <=200k? Actually we could have 7 numbers if we avoid the combination that exceeds 200k? But we need each a_i to be some product of m-1 primes from a set of m primes. If we choose m=7, one of those products (excluding the smallest prime) may exceed 200k, but we could choose a different set of primes that are not the first primes? For example, choose primes like 2,3,5,7,11,13,17? Already did. Excluding 2 gives product ~255k >200k. So that a_i would be invalid. So we cannot have that number. But we could choose a set of 7 primes that are all larger? That would increase product. So likely maximum m is 6. So the number of distinct gcd values after removal along a path could be up to maybe 6? But could there be other constructions yielding more distinct gcd values using numbers within 200k? For example, using numbers that are powers of 2? Let's see: a_i = 2^i? But gcd of all except one: if numbers are 2,4,8,16,... The gcd of all is 2. Removing the smallest yields gcd of larger numbers maybe larger? Actually, gcd(4,8,16)=4, gcd(2,8,16)=2, gcd(2,4,16)=2, gcd(2,4,8)=2. So only 2 and 4. Not many.

    Another approach: The number of distinct values from gcd of subsets of a set of numbers bounded by M is at most O(sqrt(M))? Not sure.

    Given constraints (2e5), many solutions use the approach of storing a map of gcd -> count, with size O(log maxA) per node. I've seen similar problem "Maximum GCD after at most one removal" on trees. The typical solution is: Do DFS, maintain a map from gcd value to minimal depth (or something) to allow one skip. Actually, I recall a solution for problem "GCD on a Tree" from Codeforces Round #1036 (Div. 2) maybe? Let's search memory: There is Codeforces problem "GCD on a Tree" where you have to compute for each node the maximum gcd possible if you can change one node to 0. I think it's CF #1107? Not sure.

    But let's derive a solution using the two-state DP with sets. Since the number of distinct gcd values in these sets is small (practically O(log maxA)), we can maintain them as vectors of pairs (gcd, maybe count) but we just need the set of possible gcds after one skip. At each node, we compute new set from parent's set. Since the size is small (like at most 60 maybe), we can propagate. Let's try to bound the size.

    We have two types of values:

    • Values from dp1[parent] after gcd with a_u.
    • Value from g0[parent] (skip current).

    The dp1[parent] itself came from previous steps. Let's attempt to bound the number of distinct gcd values that can appear in dp1 along a path. Each dp1 value is gcd of some subsequence of the path with exactly one omission. That is essentially gcd of the entire path except one vertex. There are at most depth such possibilities (one for each omitted vertex). But many may coincide. However, could there be O(depth) distinct values? Let's try to construct a sequence within 200k that yields many distinct gcds after omitting each element. We need gcd(all except i) to be distinct for each i. As argued, each such gcd must be a divisor of the product of all numbers, but more importantly, each such gcd is a common divisor of all numbers except a_i. Since numbers are bounded, the total number of distinct divisors across all numbers is limited per number, but across different i the gcd could be different divisors of a particular set.

    Consider using numbers that are powers of distinct primes? For example, take a_i = p_i (distinct primes). Then gcd(all except i) = 1 because any two primes are co-prime. So all 1.

    Maybe use numbers that are multiples of some primes but each omits a different prime factor, as earlier. That yields distinct gcds equal to the omitted prime. So to get many distinct gcds, we need many distinct primes whose product (of all but one) is within 200k. As we saw, maximum number of primes we can have such that the product of (k-1) of them is ≤ 200k is limited. The product of the smallest (k-1) primes grows quickly. Let's find max k such that the product of the first (k-1) primes ≤ 200k. For k=7, the product of the first 6 primes (2,3,5,7,11,13) is 30030, which is ≤200k. For k=8, product of first 7 primes (2,3,5,7,11,13,17) = 510510 >200k, but we could choose a different set of 7 primes where the product of the 6 smallest among them is ≤200k? If we want 8 numbers (k=8), we need 8 primes; each a_i is product of 7 primes (excluding one). The smallest possible maximum product of 7 primes among 8 primes is achieved by taking the 8 smallest primes? That would be product of the 7 smallest (excluding the largest) = product of first 7 primes = 510510 >200k. So cannot have all 8 numbers ≤200k. So k <=7. But we need each a_i to be product of all primes except one; that's just one construction. Perhaps there are other constructions not based on primes that yield many distinct gcds. For example, using numbers that are multiples of 2, but with different exponents: a_i = 2^i. gcd(all except i) = 2^{min among others} = if i is the index of the smallest exponent, then gcd = 2^{second smallest}, otherwise gcd = 2^{smallest}. So only two distinct values. Not many.

    Maybe using numbers that are like: a1 = 23, a2 = 25, a3 = 35, a4 = 27, a5 = 37, a6 = 57, etc. Let's try to see distinct gcd after omission. The gcd of all numbers is 1. If we omit a particular number, the gcd might become something like a prime factor common to all others. Could we get as many distinct as number of primes? Possibly, but each a_i is product of two primes? Then gcd of all except one could be a prime if that prime is common to all others. To have distinct for each i, we could assign each i a unique prime p_i, and ensure that all numbers except a_i are multiples of p_i. That means for each prime p_i, all a_j for j != i must be divisible by p_i. That implies that for any two distinct primes p_i and p_j, a_i must be divisible by p_j (since i != j, a_i is among "all except j" so must be divisible by p_j). So each a_i must be divisible by all primes except p_i. So a_i = product of all primes except p_i. That's exactly the earlier construction. So that's the only way to have each omission yield a distinct prime. So maximum number of distinct primes we can have is limited by product constraint. So maximum distinct gcds from such a construction is at most 7 maybe. So the number of distinct values for dp1 along a path is bounded by about 160? But can it be higher using composite numbers with many divisors? For example, if numbers are all the same? Then all gcds are same. If numbers are varied, but the gcd after omission might be a divisor that could be many different numbers, but each such divisor is a common divisor of almost all numbers. The set of possible gcd values is limited by the number of divisors of the first number? Not necessarily, because if we skip the first number, the gcd could be something that does not divide the first number. So dp1 values could be divisors of later numbers. However, consider that dp1 values are obtained by taking gcd of a set that is either the whole path except some node. The gcd of a set is a divisor of every element in that set. So it must be a divisor of the second element (if the set includes it). For each node index i, the gcd after removing i is a divisor of a_{i+1} (if i+1 exists) and also of a_{i-1} etc. But it must be a common divisor of all except i. So it's a divisor of the intersection of the divisor sets of all those numbers. The total number of possible distinct numbers that can be the gcd of such subsets may be larger.

    Let's try a brute force thought: Let's suppose we have numbers: 1, 2, 3, 6, 12, 24,... Actually, we can get many divisors? For a path of length L, the set of gcd values after omission is the set of numbers that are common divisors of all but one element. Each such number is a divisor of all numbers except possibly one. Since each number is at most 200k, each has at most about 160 divisors. The set of possible gcd values is subset of the union of divisors of each number. But could there be up to 160*L? Possibly many distinct divisors across numbers, but can a single path produce many distinct gcd values? For each omitted index, the gcd is a common divisor of all numbers except that index. That common divisor must divide all numbers except that one. So for each candidate divisor d, we could have at most one index for which d is the gcd? Actually, d could be the gcd after omitting several different indices? Possibly yes if skipping different indices yields same gcd. But distinct d could be many. The maximum number of distinct d that can appear as a common divisor of all but one element among a sequence of numbers might be bounded by something like O(L * log max) but maybe not huge.

    But typical solutions for this problem use a DP with map/dictionary that stores gcd values and their "count" of how many times we can skip? Actually, there is known problem: "GCD on a Tree" where you can change one value to zero, and they use DFS with two maps: one for gcd without any zero, and one for gcd with exactly one zero. The sizes are small because each time you take gcd the number of distinct values reduces. Many participants used this method. Let's recall: For each node, they maintain a map from gcd value to the minimum number of changes used (0 or 1) to achieve that gcd? Or simply a set. They then combine children? Actually, the path from root to node is linear, so we can just maintain two states.

    Simpler approach: Since we only care about the maximum possible beauty, we can compute for each node the answer as max( pref[node], something from parent's answer? Not directly.

    Alternative approach: We can compute for each node the answer using two DFSes: one computes prefix gcd, and the other computes something like "best after skipping". There is known technique: For each node, we can compute the answer as max( pref[node], gcd_of_children_with_skip? Not that.

    Maybe we can compute for each node the gcd of the entire tree except that node? No.

    Let's think about using the divisor condition. For each divisor d, we want to know, for each node, the number of vertices on its path that are not divisible by d. If that count <= 1, then d is achievable. So answer for node is max d such that on its path, number of non-divisible <= 1. Since d can be up to 2e5, we could for each node compute the minimum "non-divisible count" over all d? Actually, we want maximum d.

    We could do a DFS and maintain an array cnt[d] that counts the number of vertices on current path that are NOT divisible by d. When we go into a node, for each divisor d of a_u, we need to update? Actually, for a given d, we want to know how many vertices on the path have a_i % d != 0. When we add a node u, for all d that divide a_u, the count cnt[d] does not change (since a_u is divisible by d). For d that do NOT divide a_u, cnt[d] increases by 1. So we need to, for each node, know which d's to increment. That's problematic if we have to increment for many d (i.e., those d that do not divide a_u). Instead, we could think of enumerating divisors of a_u and updating only those that divide? Actually, we need to increment for all d except divisors of a_u. That's huge.

    We could invert: maintain for each d the count of "bad" nodes (non-divisible).