Блог пользователя VitSalis

LCA problems
Автор VitSalis, 11 лет назад, По-английски

Hello everyone. Recently I tried to learn LCA from the topcoder tutorial. I have solved 1 problem (spoj.com/problems/QTREE2) and now I am looking for some other beginers problems. Do you have any suggestions?

Теги lca
  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://acm.timus.ru/problem.aspx?space=1&num=1471 -- analog of spoj problem

http://acm.timus.ru/problem.aspx?space=1&num=1752 -- more difficult

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Also http://acm.timus.ru/problem.aspx?space=1&num=1699

    → Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    I have been thinking abt 1752 and came up with an idea. And Im interested in if it is correct:

    1) using memoization and several sophisticated DFS I will determine for every (u,v) edge ((v,u) being different) longest vertex from u going through v, thereby easily calculating longest vertex from u. hope it is O(N).

    2) Then I will make parents array: DP[i][j] = 2^j-th parent from i. (N*Log(N))

    3) for every query, determine LCA in (logN) and if d>max(distance(u, LCA(u, longest_from_u)),distance(u, LCA(u, longest_from_u))) then gradually decrease distance between u and LCA(u, longest_from_u) until we reach wanted vertex. else Well if all above is correct there is not really a need to write any more :D.

    is it correct? : ))

    is there better solution?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      Great spoiler is here

      → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I have a confusion about step 1.The longest distance from any to any other node may change when you change the root.think about a complete binary tree with 7 nodes considering 1 as root ((1),(2,3),(4,5,6,7)). the longest distance from any node found by dfs(1) call will return you at most 2 . But if you start dfs from a leaf node does everything remain same??? no, the other leafs are now at distance 4. Am I right?

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I didnt understand what you said cuz Im stoned right now. But i can tell I solved using the spoiler mentioned by dalex.

        → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

http://codeforces.com/problemset/problem/192/E

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this is just LCA problem LCA

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here are some more http://www.lightoj.com/volume_problemcategory.php?category=Range%20Minimum%20Query/Lowest%20Common%20Ancestor

(Need to register first)

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://www.spoj.com/problems/LCA/ this problem is based only on lca.

→ Ответить