Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 1099 (Div. 2)
E. Graph Cutting Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes → Virtual participation
For his birthday, young Fedya was given a tree with n vertices and a chainsaw. He wants to Virtual contest is a way to take part in past
contest, as close as possible to participation
cut out a connected subgraph from it. Fedya decided to act as follows: he chooses three
on time. It is supported only ICPC mode for
distinct vertices a, b, c (a < b < c), and cuts out the minimal connected subgraph containing virtual contests. If you've seen these
problems, a virtual contest is not for you -
all three vertices. He wants the size of the resulting subgraph to be exactly d (that is, the
solve these problems in the archive. If you
number of vertices in the cut-out subgraph must be equal to d ). just want to solve some problem from a
contest, a virtual contest is not for you -
solve this problem in the archive. Never use
He became interested in how many different such subgraphs he can cut out. Subgraphs are someone else's code, read the tutorials or
considered different if the chosen triples of vertices are different. Help him solve this problem! communicate with other person during a
virtual contest.
Input Start virtual contest
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 500 ). The description of the test cases follows.
The first line of each test case contains two integers n and d (3 ≤ d ≤ n ≤ 2000 ) — the → Problem tags
number of vertices in the tree and the desired size of the cut-out subgraph.
dfs and similar dp math trees *2300
Then follow n − 1 lines, each containing two integers u and v (1 ≤ u, v ≤ n, u ≠ v ), No tag edit access
meaning the vertices connected by the corresponding edge. It is guaranteed that the given
graph is a tree.
→ Contest materials
It is guaranteed that the sum of n over all test cases does not exceed 2000 .
Announcement (en)
Output Editorial (en)
For each test case, output a single number — the number of different subgraphs that Fedya
can cut out.
Example
input Copy
3
4 3
1 2
3 1
4 1
5 5
1 2
2 4
2 3
5 1
7 7
1 2
1 3
2 4
2 5
3 6
3 7
output Copy
3
1
0
Note
This is what the tree looks like for the first test case:
The following triples are suitable: (1, 2, 3 ), (1, 2, 4 ), (1, 3, 4 ). But for the triple (2, 3, 4 ), the
size of the connected subgraph is 4.
This is what the tree looks like for the second test case:
For it, only the triple of vertices (3, 4, 5 ) is suitable.
This is what the tree looks like for the third test case:
It can be shown that no triple is suitable for this subgraph.
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/03/2026 20:16:33UTC-6 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by