You are not logged in. Please login at www.codechef.com to post your questions!

×

ACM14AM2-Editorial

PROBLEM LINK:

Practice
Contest

Author:
Tester:
Editorialist: Jingbo Shang, Anudeep

DIFFICULTY:

Medium

PREREQUISITES:

Segment Tree, Depth First Search Order

PROBLEM:

Given a rooted tree (actually incrementally growing by add some new leaves on the current one), count how many unordered node pairs (P, Q) such that the P and Q are both in the subtree rooted at the given node V, and Distance(P, Q) is even. Distance(X, Y) = Number of roads in the unique path from X to Y, if the given road network were bi-directional.

EXPLANATION:

Offline Idea

Although the tree is growing along time, we can first load all operations and construct the final tree we will have. Therefore, we can solve this problem using an offline algorithm by activating the node one by one and maintaining some data structure.

Depth First Search Order

Because the query is about the subtree, it is natural to think about the depth first search (DFS) order of the tree, which could help us keep the nodes of a subtree in a consecutive interval. For example, the following tree’s DFS order is: 1 2 5 7 8 3 4 6, where all subtrees are consecutive intervals.

alt text

Specific Query Solution

Then, considering the specific query problem, it is equivalent to the problem that asking how many nodes are there in the subtree rooted at V and their distance to V has the same parity. That is, if there are A nodes at an even distance from V, then picking any two of them is valid; if there are B nodes at an odd distance from V, the situation is same. Therefore, answer = A * (A - 1) / 2 + B * (B - 1) / 2.

Well, the problem is transformed to count the number of nodes in the subtree rooted at node V have odd/even depth, because same depth lead to same parity. As we already constructed the tree, the depth information is observed. And the subtrees are consecutive in the dfs order. Take the odd depth as an example. When a node with odd depth is activated (i.e. added by the operation), we add 1 on its position in the dfs order. And the range sum query on the dfs order can help us the find out the number B. Similarly, A can be maintained too.

Data Structure Choices

To achieve the efficiency requirement, two segment trees (for odd and even depth separately) could be adopted to do the add/sum queries, such that the overall time complexity leads to O(NlogN), where N is the total number of operations.

AUTHOR'S AND TESTER'S SOLUTIONS:

The links will be fixed soon.

Author's solution can be found here.
Tester's solution can be found here.

asked 10 Nov '14, 10:50

shangjingbo's gravatar image

3★shangjingbo ♦♦
161446376
accept rate: 0%

edited 10 Nov '14, 11:51

admin's gravatar image

0★admin ♦♦
19.8k350498541


"Links will be fixed soon" has not been rectified yet. The problem's practice page is not working, for the submissions. Please fix the links. Thanks.

link

answered 10 Oct '15, 19:15

awhitesong's gravatar image

1★awhitesong
1
accept rate: 0%

edited 10 Oct '15, 21:34

have patience Dhawal :)

link

answered 10 Oct '15, 19:49

s24w's gravatar image

4★s24w
456
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×15,852
×2,655
×1,767
×1,112
×54
×15

question asked: 10 Nov '14, 10:50

question was seen: 3,582 times

last updated: 10 Oct '15, 21:34