SliferSkyd's blog

Need help in a tree problem
By SliferSkyd, history, 3 years ago, In English

Hello everyone, can you help me with this problem:

Given a tree has N vertice (N <= 3*10^5) and a number K (K <= n — 1). Each edge in this tree has a weight W (- 10^6 <= W <= 10^6).

You should choose exactly K edges that the sum of their weight is maximum and mustn't choose 2 edges that connect with the same vertex.

I think with N and K small, this problem can be solved using dp.

Thanks!

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A very wild guess, but I'd try to think if aliens trick (aka Lagrange multipliers) works here.

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

https://codeforces.net/gym/102331/problem/J

→ Reply