All Tracks Algorithms Graphs Depth First Search Problem

Largest Windmill
Tag(s):

Algorithms, Medium

Problem
Editorial
Analytics

We define a windmill graph as a graph G centered on node $$c$$ with at least $$5$$ adjacent paths. One of these paths has to have length at least $$3$$ and it is interpreted as the base of the windmill. The remaining paths have length exactly $$1$$ and are interpreted as the sails of the windmill.

For example, the graph given below is a windmill with $$8$$ nodes centered on node $$1$$ with $$5$$ adjacent paths and the base of length $$3$$.

       2      3 
         \   /
    5 ---- 1 -----4
           |
           6
           |
           7
           |
           8

For a given tree $$T$$ with $$N$$ nodes, the goal is to find the size of its largest subgraph (in terms of the number of nodes) which is a windmill graph and it’s center vertex. If there are many such largest subgraphs, take the one with the smallest center vertex. If no windmill graph is a subgraph of $$T$$, then the answer is $$-1$$.

Constraints:

$$1 \leq N \leq 10^5$$

Input format:

On the first line, there is a single integer $$N$$ denoting the number of nodes in the tree $$T$$. Then, $$N-1$$ lines follow. Each of them contains two space-separated integers $$u$$ and $$v$$ and denotes that there is an edge between nodes $$u$$ and $$u$$ in the tree.

Output format:

If there is no subgraph of $$T$$ which is a windmill graph output $$-1$$ in a single line. Otherwise, output two space-separated integers $$result$$ and $$c$$, where $$result$$ is the size of the largest windmill subgraph of $$T$$ and $$c$$ is the smallest center node among all the largest windmill subgraphs of $$T$$.

SAMPLE INPUT
8
1 2
1 3 
1 4
1 5
1 6
6 7
7 8
SAMPLE OUTPUT
8 1
Explanation

The graph is the same as the example windmill graph described in the statement.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications