Trees AgainProblem code: TREES |
All submissions for this problem are available.
Given a tree, you need to count how many subtrees exist such that the length of the longest path in the subtree is at most K.
Input :
The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and K. The following N - 1 lines contain two integers ai and bi, indicating an edge between nodes ai and bi in the tree. There is a blank line after each test case.Output :
Output T lines, one corresponding to each test case, containing the required answer.
Sample Input : 2 3 1 0 1 1 2 6 3 0 1 1 2 2 3 2 4 3 5
Sample Output : 5 23
Constraints : 1 <= T <= 2000 2 <= N <= 60 0 <= ai,bi < N 1 <= K <= N - 1
| Author: | syco |
| Date Added: | 20-08-2010 |
| Time Limit: | 1 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
can i assume, by the very
can i assume, by the very definition of tree, the tree as well as subtrees are connected .. ??
Thank u
The examples don't make
The examples don't make sense. The number of subtrees cannot exceed the number of nodes (excluding the empty subtree). You have exactly one subtree rooted at each node. For the first example, there are only 3 subtrees (including the original tree) with maximum path lengths of 2, 1, and 0, which should yield a result of 2, rather than 5.
@scott subtrees with max path
@scott
subtrees with max path length 0 are 0, 1, 2
subtrees with max path length 1 are {0,1} and {1,2}
If that's the case, I think a
If that's the case, I think a better term would be subgraph, rather than subtree. {0}, {1}, and {0, 1} shouldn't be considered subtrees.
@Scott :
@Scott : http://mathworld.wolfram.com/Subtree.html
Is a test case like: 3 1 0
Is a test case like:
3 1
0 1
2 1
i.e, a disconnected one ?? Hope a tree is at least weakly connected.
who can explain the output
who can explain the output for the second test case?
I can get only 20 subtrees.
0,1,2,3,4,5,
01,12,23,24,35,
012,123,124,235,324,
0123,0124,1235,4235
1234, 01234, 12345
1234, 01234, 12345
A directed tree is
A directed tree is a directed graph which would be a tree if the directions on the edges were ignored. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence).
Can we assume the first part of the definition .. ??
How many subtrees should i
How many subtrees should i get for the following test case: ( Tell if this case is valid )
3 1
0 1
2 1
is it {0}, {1}, {2}, {0,1}, {2,1}, {0,1,2}
should {0, 1, 2} included ?? please help
@ govardhan reddy your
@ govardhan reddy
your example does not satisfy the property of tree
Thanks for ur reply atul So I
Thanks for ur reply atul
So I can assume, all the nodes are reachable from at least one node of the tree. Can I assume that node as '0' ??
@liubiaoyong: the cases u
@liubiaoyong: the cases u have presented are only paths. Ofcourse they are subtrees, but u have missed few other subtrees too. like 1234, 12345, 01234. in these subtrees too the longest path doesnt exceed 3.
@ govardhan reddy you don't
@ govardhan reddy
you don't have to assume the root node of given tree it's given in the edge list.
According to wiki, "a tree is
According to wiki, "a tree is an undirected graph in which any two vertices are connected by exactly one simple path.".
But you say that input
3 1
0 1
2 1
does not satisfy the property of tree.
So are trees in this problem directed or undirected?
(
for example for input
3 1
0 1
0 2
will be subtree {0, 1, 2} included in answer? (for directed tree it will be (max path length is 1), for undirected - won't (max path length will be 2))
)
If they are directed, is this statement correct for author's definition of tree: "the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence)." ?
So final questions about
So final questions about problem statement:
1) Are tree and subtrees connected (at least weakly)?
2) Are trees directed or undirected?
3) Can we assume that tree contains vertex v, such that for any other vertex u, there is exactly one directed path from v to u? (Arborescence)
Examples of input in problem statement don't help in any of these questions.
Trees are undirected as
Trees are undirected as problem says.
@Burkadov 1) The subtree has
@Burkadov
1) The subtree has to be connected by definition.
2) Undirected.
3) Yes.
@Anshuman: please tell if
@Anshuman: please tell if this is a valid input or not.
3 1
0 1
2 1
It was mentioned above that
It was mentioned above that input
3 1
0 1
2 1
"does not satisfy the property of tree".
Can author comment on it?
@Burdakov Daniel It satisfies
@Burdakov Daniel
It satisfies the properties of a tree!
Codechef Can categorize the
Codechef Can categorize the problems based on difficulty level ,so that beginners can spend time on easy and medium problems ,,Just rating the problem will help us
@radhakrishnan After contest,
@radhakrishnan
After contest, the problems will be put into different problemset categorized by difficulty.
To practice, go to the practice section, and choose the difficulty you want.
But during the contest, I think it is part of the challenge to recognized the difficulty of the problem.
Is a tree itself considered
Is a tree itself considered a subtree of it ?
trees... again... :D
trees... again... :D
@Moshiur Yes. Subtree is
@Moshiur Yes. Subtree is basically a connected subset of edges from the tree.
can anybody tell me how we
can anybody tell me how we can down our time limit??
2nd test case not
2nd test case not clear
@Przemyslaw
as o/p sugg by u include 01234, 12345
how it can b valid as max length for 2nd test case is 3
and 01234, 12345 gives length of 4
plz anybody clarify
No, those two subtrees have a
No, those two subtrees have a maximum path length of 3. What path do you think has a length of 4?
Is 0 the root of the
Is 0 the root of the tree??
If not then what is?
The tree is not considered
The tree is not considered rooted.
Thanks Stephen Just one more
Thanks Stephen
Just one more thing does it means that the subgraph {3,2,4} in second example has maximum length of 2??
Yes, because path 3-2-4 has
Yes, because path 3-2-4 has length 2.
@stephen path 12345 has
@stephen
path 12345 has length 5
how it is 3
plz clarify
12345 is not a path. There
12345 is not a path. There isn't any edge from 3 to 4 or 4 to 5. If there were, it would be a path of length 4.
Do we have to print a modulo
Do we have to print a modulo or will the answer always fit into integer?