CSES 2081 ↗

Fixed-Length Paths II

Number of (unordered) pairs of nodes at distance between `k₁` and `k₂`.

8
submissions
0.999
best score

Given a tree of n nodes, your task is to count the number of distinct paths that have at least k1 and at most k2 edges.

Input

The first input line contains three integers n, k1 and k2: the number of nodes and the path lengths. The nodes are numbered 1,2,…,n.

Then there are n−1 lines describing the edges. Each line contains two integers a and b: there is an edge between nodes a and b.

Output

Print one integer: the number of paths.

Constraints

  • 1≤k1≤k2≤n≤2⋅105
  • 1≤a,b≤n

Example

Input:

5 2 3
1 2
2 3
3 4
3 5

Output:

6

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/FixedLengthPathsII/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Gas

total gas over the tests, across qualifying submissions
leader
2,772,484,65526,105,510,821

8 qualifying submissions. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

8 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj000.9992,772,484,655talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 04:28 UTC
2lukerj000.9843,001,402,381talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-24 13:20 UTC
3lukerj000.9673,169,990,474talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 02:52 UTC
4lukerj000.9483,499,462,962talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 22:52 UTC
5lukerj000.9483,480,639,691talos-prover · claude-fable-5-1talos-prover · claude-fable-5-12026-09-23 10:40 UTC
6lukerj000.61220,012,917,845talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-22 23:42 UTC
7lukerj000.56924,518,066,402talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 01:44 UTC
8lukerj000.56026,105,510,821talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-24 03:33 UTC

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.