树中u-v路径乘积的约数个数高效查询方案求助

Problem Statement #

Given a tree with N vertices and N-1 edges, each vertex v has a value C[v]. We need to handle Q queries, each giving u and v. Define A as the product of all node values on the simple path from u to v (i.e., if the path is [u,a,b...,v], then A = C[u]*C[a]C[b]...*C[v]). We need to output the number of divisors of A, modulo 1e9+7.
Constraints: 1≤N,Q≤100000, 1≤C[i]≤1000000 (1≤i≤N).

My Initial Approach & Its Flaws #

I recognized direct product computation was infeasible, so I focused on prime factor counts:

• Precomputed LCA using binary lifting for path queries.
• Used a map<int, int> for each node to store prime factor counts of the root-to-node product, built via DFS and sieve-based factorization.
• For queries, calculated path prime counts by subtracting LCA's map from u and v's maps, then applied the divisor count formula: if ( K = a^p * b^q * c^r... ), divisor count ( D = (p+1)(q+1)(r+1)... \mod 1e9+7 ).

Why This Fails #

The time complexity is prohibitive:

• Let M be the number of primes ≤1e6 (~78,498). DFS takes ( O(N*M) ), and each query takes ( O(M+logN) ). For N=1e5 and Q=1e5, this results in ~7e9 operations—way beyond time limits.

Optimized Solution: Mo's Algorithm on Trees #

The key insight is leveraging the fact that each number ≤1e6 has at most 7 distinct prime factors, combined with Mo's algorithm to handle path queries efficiently.

Step 1: Precompute Helper Data #

1. Smallest Prime Factor (SPF) Sieve: Precompute the smallest prime factor for every number up to 1e6. This allows factorization of any C[v] in ( O(log C[v]) ) time.
2. Euler Tour & LCA:
   • Perform a DFS to record in-time (entry) and out-time (exit) for each node, plus depth and parent arrays for binary lifting (to compute LCA in ( O(logN) ) per query).
   • Path representation rules:
     • If LCA(u,v) = u: path corresponds to the range [in-time[u], in-time[v]] in the Euler Tour array.
     • Else: path corresponds to [out-time[u], in-time[v]] plus the LCA node.

Step 2: Sort Queries for Mo's Algorithm #

• Split the Euler Tour array into blocks of size ( \sqrt{N} ).
• Sort queries using:
  • Block number of the left endpoint as the primary key.
  • For even blocks, sort by right endpoint ascending; for odd blocks, sort descending (reduces pointer movement overhead).
• Track whether each query needs to include the LCA node.

Step 3: Process Queries with Mo's Algorithm #

Maintain these state variables:

• cur_l/cur_r: Current window pointers in the Euler Tour array.
• ans: Current divisor count modulo 1e9+7.
• freq: A hash map tracking total exponents of each prime in the current window.
• in_window: Boolean array tracking if a node is active in the window.
• Precomputed modular inverses for numbers 1-21 (since maximum exponent+1 for any prime in C[v] is ~20).

Core Operations

• Add a node: Factorize C[node], update ans by multiplying with the inverse of the old (exponent+1), increment the prime's exponent, then multiply by the new (exponent+1).
• Remove a node: Reverse the add operation—multiply by the inverse of the current (exponent+1), decrement the exponent, then multiply by the new (exponent+1).
• Adjust window: Move cur_l and cur_r to the query's range, toggling nodes in/out of the window as needed.
• Handle LCA: For queries requiring the LCA, temporarily add it to the window, compute the answer, then revert the state.

Time Complexity #

• SPF sieve: ( O(1e6 log log 1e6) )
• LCA precomputation: ( O(N logN) )
• Query sorting: ( O(Q logQ) )
• Mo's processing: ( O((N\sqrt{N}) log C[v]) ) → ~3e7 operations for N=1e5, which is feasible.

内容的提问来源于stack exchange，提问作者Sanjeev Maheshwari