bao987's blog

Count the number of segments [l, r] that satisfy the condition.
By bao987, history, 7 months ago, In English

Given a tree consisting of M vertices and N-1 weighted edges. The edges are numbered from 1 to N-1; the i-th edge connects the pair of vertices (u, v) and has weight c.

The path cost between two vertices (u, v) is the sum of the weights of the edges on the path from u to v (u ≠ v). If there is no path from u to v, the path cost for the pair (u, v) is 0.

An edge deletion method is described as follows:

Choose two positive integers L, R satisfying 1 ≤ L ≤ R ≤ N — 1;

Delete all edges numbered from L to R;

Given a positive integer K. An edge deletion method is called "beautiful" if every path cost between any pair of vertices does not exceed K. Two edge deletion methods are considered different if there is an edge present in one method but not in the other.

Requirement: Count the number of "beautiful" edge deletion methods. Constraints: N <= 1e5 Time limit: 1-2s

Sample input: 6 12

1 2 3

1 4 5

2 3 6

2 5 4

3 6 9

The answer is 9.

Please help me with this problem. Thank you very much. Here is the code for my smaller subtasks. Link: https://ide.usaco.guide/OaV3EO7Zu9DRl2APo19

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

»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

maybe you missed to provide the edges for the example

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

    Sorry, I forgot.
    This is the original explanation table.

    L, R Selection Explanation
    L = 1, R = 1 Delete edge 1. This is not a “beautiful” deletion because there exists a path from vertex 2 to vertex 6 with a total weight of 15, which is greater than K = 12.
    L = 1, R = 2 Delete edges 1 and 2. This is not a “beautiful” deletion because there exists a path from vertex 2 to vertex 6 with a total weight of 15, which is greater than K = 12.
    L = 1, R = 3 Delete edges 1, 2, and 3. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
    L = 1, R = 4 Delete edges 1, 2, 3, and 4. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
    L = 1, R = 5 Delete edges 1, 2, 3, 4, and 5. This is a “beautiful” deletion because there are no remaining paths between any pair of vertices.
    L = 2, R = 2 Delete edge 2. This is not a “beautiful” deletion because there exists a path from vertex 5 to vertex 6 with a total weight of 19, which is greater than K = 12.
    L = 2, R = 3 Delete edges 2 and 3. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
    L = 2, R = 4 Delete edges 2, 3, and 4. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
    L = 2, R = 5 Delete edges 2, 3, 4, and 5. This is a “beautiful” deletion because the heaviest path is from vertex 1 to vertex 2 with a weight of 3, which does not exceed K = 12.
    L = 3, R = 3 Delete edge 3. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
    L = 3, R = 4 Delete edges 3 and 4. This is a “beautiful” deletion because the heaviest path is from vertex 3 to vertex 6 with a weight of 9, which does not exceed K = 12.
    L = 3, R = 5 Delete edges 3, 4, and 5. This is a “beautiful” deletion because the heaviest path is from vertex 2 to vertex 4 with a weight of 9, which does not exceed K = 12.
    L = 4, R = 4 Delete edge 4. This is not a “beautiful” deletion because there exists a path from vertex 4 to vertex 6 with a total weight of 23, which is greater than K = 12.
    L = 4, R = 5 Delete edges 4 and 5. This is not a “beautiful” deletion because there exists a path from vertex 3 to vertex 4 with a total weight of 14, which is greater than K = 12.
    L = 5, R = 5 Delete edge 5. This is not a “beautiful” deletion because there exists a path from vertex 3 to vertex 4 with a total weight of 14, which is greater than K = 12.
    → Reply
»
7 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply