Ahmed_Morsy's blog

non-Beard Graph
By Ahmed_Morsy, 9 years ago, In English

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 ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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).

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u explain solution with HLD?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          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.

          → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply