PraveenDhinwa's blog

Any hint/idea to solve CNTTREE spoj
By PraveenDhinwa, 13 years ago, In English

Hi, I am unable to find some idea to solve problem http://www.spoj.com/problems/CNTTREE/. I think that this is a dp problem. But no idea how can I find it's states of dp. Could anybody help me with just the state part??

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
13 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

This problem seems interesting, I'll try to solve it.

but why there is no modulo number? do we have to output the exact number?

then we should use some bignum and that's annoying specially for C++ coders

→ Reply
  • »
    »
    13 years ago, hide # ^ |
     
    Vote: I like it +6 Vote: I do not like it

    The input is a tree. A naive implementation of the subsets of all edges in the graph is 2^(N-1) where N is the number of vertices in the tree. So the answer will easily fit into a 64 bit signed integer without much analysis.

    → Reply
»
13 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I didn't solve it, but this is my idea. Fix the diameter between every two nodes (i,j). Then, try counting how many subtrees have that diameter. You can attach new nodes to any of the nodes between i and j (exclusive, because attaching a node to i or j would increase the diameter). There are some details that still need to be figured out. I'll try to solve it in the near future.

→ Reply
»
13 years ago, hide # |
← Rev. 5  
Vote: I like it +1 Vote: I do not like it

select a root node, let it be first vertex.
during DFS calculate for each vertex x values d[x][MaxDepth][MaxDiameter] (0 <= MaxDepth <= n, 0 <= MaxDiameter <= n) — how many subtrees with root x there is, with maximal depth MaxDepth and maximal diameter MaxDiameter. Inside a DFS function you know all matrices of childs of root x. There is simple dp to combine results for childs dd[indexOfAChild][MaxDepth][MaxDiameter]
UPD: Code

→ Reply