Task DescriptionDiscussion (0)

The first line of the standard input contains two space-separated integers

To the first line of the standard output you should print the count of the simple chains with the described property. The result should be printed with modulo 321555123.

Explanation:

Each simple chain of length 2 is the solution:

1 - 2 - 4; 2 - 4 - 8; 2 - 4 - 9; 8 - 4 - 9; 2 - 1 - 3; 5 - 1 - 2; 3 - 1 - 5; 1 - 5 - 7; 5 - 7 - 6.

Explanation:

Resulting simple chains are:

4 - 5; 6 - 7 - 8 - 9; 8 - 9 - 10.

Task :: z-sumpaths

You are given an undirected weighted tree with

**N**nodes. You should count the number of simple chains in the tree such that the sum of edges of particular simple chain is exactly**M**. Output the result with modulo 321555123**INPUT:**

The first line of the standard input contains two space-separated integers

**N**(2 <=

**N**<= 50 000) and

**M**(1 <=

**M**<= 100). Each of the next

**N**- 1 lines will contain three space-separated integers

**a**,

**b**(1 <=

**a**,

**b**<=

**N**) and

**w**(1 <=

**w**<= 100), meaning that there is an edge {

**a**,

**b**} with the cost

**w**.

**OUTPUT:**

To the first line of the standard output you should print the count of the simple chains with the described property. The result should be printed with modulo 321555123.

Input:

Output:

**9 4**

2 1 2

1 3 2

1 5 2

5 7 2

2 4 2

4 8 2

4 9 2

7 6 2

2 1 2

1 3 2

1 5 2

5 7 2

2 4 2

4 8 2

4 9 2

7 6 2

Output:

**9**

Explanation:

Each simple chain of length 2 is the solution:

1 - 2 - 4; 2 - 4 - 8; 2 - 4 - 9; 8 - 4 - 9; 2 - 1 - 3; 5 - 1 - 2; 3 - 1 - 5; 1 - 5 - 7; 5 - 7 - 6.

Input:

Output:

**10 7**

1 2 3

2 3 1

3 4 9

4 5 7

5 6 2

6 7 1

7 8 2

8 9 4

9 10 3

1 2 3

2 3 1

3 4 9

4 5 7

5 6 2

6 7 1

7 8 2

8 9 4

9 10 3

Output:

**3**

Explanation:

Resulting simple chains are:

4 - 5; 6 - 7 - 8 - 9; 8 - 9 - 10.

Submit Solution

Available Languages

Task info

Name: | z-sumpaths |

Time: | 0.5 sec. |

Memory: | 64 MB |

#Tests: | 25 |

AddedBy: | admin |

Source: | Slobodan MitroviÄ‡ |

Task Ratings

Difficulty: | 3.4 (17 votes) |

Quality: | 3.6 (15 votes) |

Acceptance Rate

Recent Submissions

Fastest Solutions

User | Time |
---|---|

evanlimanto | 0.434 s. |

_qwAker_ | 0.487 s. |

vjudge1 | 0.506 s. |

vjudge5 | 0.529 s. |

minchurl | 0.535 s. |

plt2312 | 0.569 s. |

vjudge3 | 0.569 s. |

crusader | 0.573 s. |

vjudge4 | 0.573 s. |

vjudge2 | 0.574 s. |

Solved By