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

Автор Varun_Shah, история, 5 лет назад, По-английски

Given a tree with N nodes we are required to seperate a connected component with exactly k nodes. You are given queries specifying this k. We need to find the minimum edges to be removed for each query.
First line specifies N.
Next N-1 lines specify edges.
Next line shows Q(number of queries).
Subsequent Q lines contain k for each query.

Constraint:
N <= 3000
Q <= 3000
K <= N

Example:
Input:
5
1 2
1 3
1 4
1 5
3
1
2
4

Output:
1
3
1

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Varun_Shah (previous revision, new revision, compare).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think this is famous problem — Barricades from Poland. You can read it in book 'Looking for Challenges.

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

    Can you please elaborate if you know...

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

      Do you know O(n**3) solution ?

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

        I thought of this...

        Dp(i, j) = answer to get a connected component for j nodes considering first i children of the current node... And then some how manipulating its values to get current value

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

      O(n^3) solution — DP[v][k] = minimum edges to be removed from subtree of v to get a connected component of size k such that v is included. Now to calculate it we iterate through its childs taking some on none nodes from them. To perform that you have to calculate another internal DP something similar to knapsack. Choose nodes from that with cost DP[child][*] and ignore it with cost 1. To see O(n^2) — https://mirror.codeforces.com/blog/entry/63257

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

    can you give link of book?