JoaoM10's blog

Beard Graph
By JoaoM10, 11 years ago, In English

Hi,

I'm trying to solve problem D "Beard Graph" from round #112.

I understand the idea explained in the editorial (http://mirror.codeforces.com/blog/entry/4124) but i don't see how to use/apply a segment/fenwick tree on this problem. How can I enumerate the paths in such a way that i can use a segment tree on it?

Thanks in advance and Merry Christmas for everyone :)

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

»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

    I need to build a segment treee for every path? I understand the use of the segment tree on a single path, but i still didn't get how to make a single segment tree that cover all the paths :/

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

      You don't have to build one segment tree, build as many as you need.

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

        Should I build a segment tree for every disjoint path? I saw some implementations of this problem and they only use one segment/fenwick tree, they do some "linear arrangement" (I don't know what it does exactly)

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

          You can do one or many, whatever you find easier to do for yourself. I find approach with many segment trees easier to implement and more straightforward for this problem.

          If you want to do one segment tree then indeed you need somehow to arrange nodes. For some node A let's call root path A such a set of nodes which should be visited on the way from A to the root (maybe except for the root). Then your goal is to arrange all nodes in such a manner that the root paths for all nodes will be contiguous in that arrangement. That is something you can't do for trees without 'beard' restriction. If you will come up with such an arrangement then you will be able to apply segment tree to it.

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

            I forget that all nodes (except one) will have degree of at most 2, INCLUDING the edge from the root :)

            Now I can see how to solve it in both ways (many segment trees or just one), thanks goo.gl_SsAhv and marat.snowbear for helping me :D

            → Reply