Counting the Number of Connected Subgraphs with a Node Having the Maximum Label

Revision en1, by vamaddur, 2020-07-27 19:22:38

We are given a tree of N nodes (with integer labels 1 to N). For each node in the tree, count the number of connected subgraphs in which that node has the maximum value label.

It is not too difficult to find a quadratic time solution by rerooting the tree N times and then performing an O(N) DFS with a dynamic programming step. Is it possible to solve this problem in O(N), O(N log N), or some sub-quadratic-time-complexity though?

Tags #dynamic programing, #dsu on tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vamaddur 2020-07-27 19:22:38 514 Initial revision (published)