hriss95's blog

Interesting graph problem
By hriss95, 12 years ago, In English

Hi guys, I've encountered an interesting problem. We are given a tree with N vertices and with its edges. All edges are with length 1 and we need to find for every edge the sum of the lengths of all paths in the tree that go through this edge. As you probably assume N can be large so N^2 is not good enough.

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

Comments Comments (8)
| Write comment?
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

http://discuss.codechef.com/questions/6446/testers-editorial

This is a generalized version of your problem.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Requested value is equal to the sum of paths legnths on the one side of edge (from vertex of this edge to all other vertexes on this side of edge) times the amount of vertexes on the other side, plus vise versa product, and plus product of amounts of vertexes of both sides of edge. Both these values (sum of legnths of all paths and numver of vertexes) it is easy to find with help of dymanic programming on the tree.

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

    OK, so i have this test:

    • 5
    • 1 2
    • 2 3
    • 2 4
    • 1 5

    Can you show me about edge 1-2 because I can't figure it out...The answer is 13 but I can't get that result with your formula

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 4   Vote: I like it +3 Vote: I do not like it

      Why?
      First side (around vertex 1): 2 vertexes (1, 5), only path 1-5, sum of lenth: 1.
      Second side (around vertex 2): 3 vertexes (2, 3, 4), two paths: 2-3, 2-4, sum of length: 2.

      1*3 + 2*2 + 2*3 = 13.

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

        Yes, thank you! I just figured it out myself. Thank you anyways! Now I need to think out the dp table for the sum of lengths and everything is good.

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

          When you calculate sum of length of some vertex, for each its child add value (sum of lengths of paths from this child)+(amount of descendents of this child, including this child), because you have all same paths but each one edge longer.

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

            Yeah but if this vertex is in another edge that sum would be different and I can't afford to launch too many searches

            → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

You mean this problem 294E - Shaass the Great?

Edit: just realize this one is much harder.

→ Reply