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

non-Beard Graph
Автор Ahmed_Morsy, 9 лет назад, По-английски

in this problem (http://codeforces.com/contest/165/problem/D) there is a condition which makes it easy which is "there exists no more than one vertex, whose degree is more than two" so what if this condition didnot exist ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

I think this is a more simple variation of HLD. The quote:

there exists no more than one vertex, whose degree is more than two

means that the graph can be easily separated in chains. Find the vertex with degree greater than 2(if such a vertex exists). Then this is the beginning of all chains. If such vertex doesn't exist, find an unused vertex with degree 1 and make it the beginning of a new chain. Repeat this until all vertexes become used. Then for each chain build some data structure that can handle this queries(for example you can use a fenwick tree).

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

    I think u got me wrong I meant the problem above but with removing the condition so the graph mustn't be a group of chains

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

      Hmm, yes, I didn't understand the question. But I think if the graph is just a tree(not a beard graph), HLD does the job.

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

        Can u explain solution with HLD?

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

          Do you know what HLD is? Have you learnt it? If no, just learn it. Split the graph in chains using HLD and for each chain build a fenwick tree/segment tree where the leaves in the tree are the edges in the chain. If you have to change the color of the i-th edge, just find its chain and update the tree. If you have to answer if the path between A and B consists of black edges only, then just find the paths between A and LCA(A,B) and between B and LCA(A,B). If they consist of black edges only, then the answer is YES. Otherwise, it's NO.

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

Another option is to read the editorial where is described a similar idea to the one that I described some minutes ago.

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

You may find this helpful: http://codeforces.com/blog/entry/10025

→ Ответить