noob64678's blog

Help with the problem
By noob64678, history, 7 months ago, In English

Given a tree of n vertices (n <= 1e5) in which the edge is arbitrarily oriented. Also given q queries (q <= 1e5) in which a, b are entered. The problem is quickly answer whether there is a path from a to b.

Thank a lot for your help.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

We should divide it in components by DFS (we give number to a component so every node in same component have same number) and than just check if their numbers are the same, it would mean that they are in the same component

→ Reply
  • »
    »
    7 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Being in the same component doesn't guarantee path existing from node a to b. Consider the tree: 1 -> 2

    If we started our dfs from node 1, nodes 1 and 2 would be in the same component. But we would answer query 2 1 wrong (reporting there's a path from 2 to 1 when in fact there isn't).

    → Reply
»
7 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

find the lowest common ancestor of a and b, call it c. you can check if from a to c only contains up and from b to c only down or viceversa.

→ Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Use lca and prefixsum

The condition for a path to exist from $$$a$$$ to $$$b$$$ is:

Spoiler
→ Reply