How to solve this problem?

Правка en2, от RNR, 2019-02-19 17:04:23

Consider a directed tree say for example P1--> P2--> P3--> P4--> ... --> Pn (consider this chain for simplicity), initially, it is like this, directed and atmost one edge going into it(for some nodes there might be no outgoing edges). Here it is like if the information starts at P1 it flows till Pn, similarly, if information starts at P2 it flows till Pn. Say if information starts at Pn it ends here itself.

We have two types of queries

Query 1: We have to answer where does it end if information starts at Pi?

Query 2: We may remove any existing edge, Eg we break a link say P2--> P3

Now the chain may look like P1--> P2 and P3 --> P4 -->...--> Pn now the query 1 for P1 is P2 and query1 for P2 is also P2?

I have seen this question in one contest on some website and it is removed now if you have seen something similar you can share here.

I want to know how to solve this efficiently?

Теги directed graph, #tree, query, #question

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский RNR 2019-02-19 17:05:29 18 Tiny change: 'dge going into it(for some ' -> 'dge going out of every node(for some '
en2 Английский RNR 2019-02-19 17:04:23 446 Tiny change: '*P1**-->**P2**-->*' -> '*P1**-->***P2**-->*' (published)
en1 Английский RNR 2019-02-19 16:52:47 662 Initial revision (saved to drafts)