×

# Editorial for NINENINE - PELT2019

 1 At first, I missed the statement that graph should be connected at each step and thought of the following solution: Make bridge tree of the graph and calculate the answer corresponding to non-bridges as earlier. For bridges (let u-v), find the components (nodes in the bridge tree) in which u and v lie. Now we need to calculate the number of nodes with a given degree in the subtree of a node of bridge tree. This can be done using euler tour of the tree which is used for subtree queries. Since degree can be upto M, we can store the nodes for each degree and use binary search to get the count of nodes that belong to the subtree. Here, we do not need to worry about formation of multiple edges since it is a bridge. answered 12 Jan, 18:14 11●1 accept rate: 0% this would solve the bonus question right? (12 Jan, 18:55) panik5★ Yeah, I guess so. (12 Jan, 19:36)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,236
×864
×65
×10
×6
×2