Problem Summary

Given a tree rooted at vertex 1, a permutation is “good” for parameter K if:

  • It starts at vertex 1 and visits remaining vertices in non-decreasing order of their distance (depth) from vertex 1.
  • Consecutive elements in the permutation are at most K edges apart.

For each query K, output f(K) — the number of good permutations mod 10^9+7.

Key Insight: The Critical Parameter D

Define D as the maximum distance between any two nodes at the same depth. This determines a phase transition:

  • K < D: No valid permutation exists → f(K) = 0. The issue is that nodes at the same depth can be at distance up to D from each other (path goes through their LCA and back down), so K must be at least D to reach between them.

  • K ≥ D+1: All orderings within each depth layer are valid. f(K) = ∏ x_d!, where x_d is the total number of nodes at depth d. The worst-case distance between any two nodes at adjacent depth layers is D+1, which K satisfies.

  • K = D: At every depth d where nodes exist at depth d+1, the last node placed at depth d must be within distance D of some node at depth d+1. If the last node is too far from all nodes at depth d+1, the jump exceeds D. This restricts valid orderings from x! to y · (x−1)!, where x = total nodes at depth d and y = number of reachable nodes (those within distance D of some node at depth d+1). This correction applies at every depth d < max_depth.

Computing D

For each node v, compute the deepest node in each child’s subtree. Then among v’s children, find the two with the deepest descendants. If the second-deepest descendant is at depth second_deepest and v is at depth depth(v), then the distance between the two deepest nodes at the same depth through v is 2 * (second_deepest - depth(v)).

D = max over all v of this quantity.

Why this works: The maximum distance between two nodes at the same depth e, whose paths pass through v, goes from e → depth(v) → e, which is 2·(e - depth(v)). The deepest such depth e is limited by the second-deepest child subtree (the first deepest child provides one node, the second provides the other).

Computing Reachability for K = D

A node u at depth d can reach some node at depth d+1 within distance D if and only if there exists an ancestor of u at depth ≥ max(0, d + 1 − D/2) whose subtree contains nodes at depth d+1.

Why: The distance from u at depth d to a node w at depth d+1 through their LCA a at depth t is 2(d − t) + 1. For this to be ≤ D, we need t ≥ d + 1 − D/2. And a’s subtree contains nodes at depth d+1 iff deep_d[a] ≥ d+1.

Practical computation (O(log N) per node):

  1. For each node u at depth d, find its ancestor a at depth target = max(0, d + 1 − D/2) using binary lifting (O(log N) per node).
  2. Check if deep_d[a] ≥ d + 1. If yes, u is reachable.
  3. y = count of reachable nodes at depth d.

Iterating nodes by depth: BFS order (ord[]) groups nodes by depth. Record depth_start[d] = index in ord[] where depth d begins. Then iterate ord[depth_start[d] .. depth_start[d]+cnt[d]) — O(cnt[d]) per depth, O(N) total. Avoids the O(N·max_depth) pitfall of scanning all nodes at every depth.

Term at depth d: y · (x−1)!, where x = cnt[d], y = # reachable nodes.

When y = x (all nodes reachable), the formula equals x! — no effective correction. When y < x, the count is genuinely reduced because unreachable nodes cannot be last at depth d.

This correction is applied at EVERY depth d < max_depth, not just one. Multiple depths can simultaneously have y < x, each reducing the count independently.

Algorithm Summary

  1. BFS from root: Compute depth[v], parent[v], traversal order (ord[]), depth counts, depth boundaries (depth_start[d]).
  2. Post-order scan: Compute deepest descendant depth (deep_d[u]) for each node (reverse BFS order).
  3. Compute D: For each node v, find two children with deepest descendants. D = max over all v of 2·(second_deepest − depth(v)).
  4. Binary lifting: Build ancestor table for O(log N) ancestor queries.
  5. Precompute answers:
    • ans_full = ∏ cnt[d]! (for K ≥ D+1)
    • ans_D = ∏ y_d · (cnt[d]−1)! over all depths d < max_depth, times cnt[max_depth]! (for K = D). Use ord[] + depth_start[] to iterate only nodes at each depth.
  6. Answer queries in O(1): 0 if k < D, ans_D if k = D, ans_full if k ≥ D+1.

Complexity

  • BFS + post-order scan: O(N)
  • Computing D: O(N) (each node processed once, two-deepest scan is O(degree))
  • Binary lifting: O(N log N) preprocessing, O(log N) per ancestor query
  • K=D computation: O(N log N) (one ancestor query per node)
  • Queries: O(1) each after O(max_depth) precomputation
  • Overall: O(N log N + Q) per test case

Corner Cases

  • D = 0 (chain/tree with no branching at any depth): f(K) = 1 for all K. The product is just 1! × 1! × … = 1.
  • K = 1 for a chain starting at vertex 1: D = 0, so f(1) = 1 (the only valid permutation follows the chain, each consecutive pair at distance 1).
  • K = 1 for any branching tree: D ≥ 2, so f(1) = 0 (any branching forces a jump of distance ≥ 2 between siblings).
  • Single-node tree: D = 0, f(K) = 1 for all K.
  • Star graph (root with N−1 children): D = 2, f(1) = 0, f(K) = (N−1)! for K ≥ 2.

Implementation Challenges

  1. Correction must apply at every depth, not just one. The original code only corrected at a single “critical” depth. The constraint that the last node at depth d reaches depth d+1 can bind independently at every depth. E.g., in a tree with edges {1-2, 1-3, 3-4, 3-5, 5-6, 5-7}, both depth 1 and depth 2 have binding constraints at K=D=2.

  2. Reachability is not the same as direct parenthood. A node at depth d can reach nodes at depth d+1 through ancestors shallower than itself. With D=4, a node whose grandparent has children at depth d+1 can reach them at distance 3 ≤ D, even though the node itself has no children at depth d+1. Using only “direct parents” as y undercounts reachable nodes.

  3. The LCA can be at any depth, not just the node’s own depth. The distance from u at depth d to w at depth d+1 is 2(d − depth(LCA(u,w))) + 1. The LCA can be as shallow as the root. So reachability depends on whether any ancestor at depth ≥ d+1−D/2 has descendants at depth d+1, not just the node itself.

  4. The correct formula is y · (x−1)!, not x · (y−1)!. Semantically: pick one of y reachable nodes to be last (y choices), then freely order the remaining x−1 nodes. The formula x · (y−1)! has no meaningful combinatorial interpretation for this problem.

  5. Binary lifting is needed for efficient ancestor queries. Naive ancestor walks (walking parent by parent) could be O(N) per node in a chain, leading to O(N²) total. Binary lifting gives O(log N) per query, keeping the overall K=D computation at O(N log N).

  6. deep_d must be post-order computed. The deepest descendant depth of each subtree is needed for both computing D and checking reachability. A simple post-order BFS scan (reverse BFS order) suffices.

  7. Edge case D=0 must not cause division-by-zero or negative ancestor depth. When D=0, D/2=0, target depth = d+1, which is above the node. No ancestor exists, so y=0. But since D=0 means the tree is a chain with cnt[d]=1 at every depth, the ans_D product is just 1 (handled by the ans_full fallback since ans_D = ans_full when D=0).

  8. Avoid O(N·max_depth) when iterating nodes by depth. A naive for i in 1..N: if dep[i]==d inside a loop over depths gives O(N·max_depth) — O(N²) worst case. Fix: BFS order already groups nodes by depth. Record depth_start[d] and iterate ord[depth_start[d]..depth_start[d]+cnt[d]). Each node visited exactly once total → O(N log N) overall.