| Problem description | | Progress |
|
Темы:
Dynamic programming on subtrees
Mirko became the CEO of a large corporation. The company employs N people, who are numbered from 1 to N, and Mirko himself has number 1. All employees, except Mirko, have a boss. A boss can have several subordinates, but not more than one boss.
When Mirko receives an assignment from investors, he hands it over to his subordinate with the lowest number. That subordinate also passes it on to his lowest-numbered subordinate, and so on, until the job passes to an unlucky worker with no subordinates to complete it.
That worker gets 1 coin, his boss gets 2 coins, that boss's boss gets 3 coins, and so on. Then the one who actually did the job realizes how unfair this capitalist system is and quits the job.
Mirko receives assignments until only one employee remains in the corporation — Mirko himself. Then he completes this task, receives 1 coin and leaves the corporation.
He wondered how many coins each former employee received in total. Help him with this.
Input:
The first line contains one natural number N (1 ≤ N ≤ 2·105) — the number of company employees. The next line contains N-1 numbers a2, a3, ... an (1 ≤ a i <i), ai — number of the head of the i-th employee.
Output:
Print N numbers, the i-th number should indicate how many coins the i-th employee received.
Examples:
| Input |
Output |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Explanations:
The following is a description of the second example.
Mirko gives the first task to worker 2, who passes it on to worker 3, who completes the task. Thus, worker 3 receives one coin, worker 2 — two coins, and worker 1, Mirko himself, — three coins. After that, employee 3 quits.
Mirko gives the second task to worker 2, who passes it on to worker 4, who immediately passes the task to worker 5, who completes the task. After that, worker 5 receives one coin, worker 4 — two coins, worker 2 — three coins, and Mirko — four coins. Employee 5 quits.
After completing the third task, worker 4 receives one coin, worker 2 — two coins, and Mirko — three coins, after which employee 4 quits.
After completing the fourth task, worker 2 receives one coin, and Mirko — two coins, after which the second employee quits.
Finally, the fifth task is performed by Mirko himself, receiving one coin for this, after which the process stops.
In total, Mirko received 13 coins, an employee 2 — 8 coins, worker 4 — 3 coins, and workers 3 and 5 — one coin.
| |
![]()
|
|
Темы:
Dynamic programming on subtrees
You are given a tree (a connected acyclic undirected graph) consisting of n vertices.
Find the size of its maximum matching (the set of pairwise nonadjacent edges).
Input:
The first line contains the number n - the number of vertices in the tree.
Next comes n-1 lines, each of which contains two numbers ai and bi (1 <= ai, b i <= n) - tree edges.
Output:
Print one number - the size of the maximum matching of the given tree.
Examples:
| Input |
Output |
4
1 2
23
3 4 |
2 |
Explanation:
The maximum matching of this tree will include edges 1-2 and 3-4.
| |
![]()
|
|
Темы:
Dynamic programming on subtrees
Today, the Aisne Castle is hosting a pie festival in which n bakeries participate, each of which has its own unique number from 1 to n.
Some bakeries are connected by two-way roads, but in such a way that if it is possible to walk from bakery i to bakery j, then there is exactly one route between them.
When En eats pies in the i-th bakery, he gets Ai pleasures. And if it passes along the road between some bakeries with numbers v and u, then the delicious aroma of pies brings Cv,u pleasure.
En doesn't want to go to every bakery more than once (some may not go at all), but she wants to get the most out of the festival.
He will start at one of the bakeries and will only cross between them using the existing roads.
Help En determine the maximum possible pleasure he can get.
Input:
The first line contains the number n (1 <= n <= 50000) - the number of bakeries, and the number k - the number of existing roads between the bakeries.
The second line contains n numbers Ai (0 <= Ai <= 10000) - the pleasure of pies in the i-th bakery.
Then k lines follow, each containing 3 numbers v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000), meaning that there is a road between bakeries numbered v and u, and the aroma on this road brings C pleasure.
Output:
Print one number - the maximum possible satisfaction.
Examples:
| Input |
Output |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
Explanations:
In the first example, you need to start at the 1st bakery (1 treat), walk along the road between the 1st and 2nd bakeries (1 treat), and visit the 2nd bakery (1 treat). Total pleasure - 1+1+1 = 3.
In the second example, you need to start at the 5th bakery (10 pleasures), walk along the road between the 5th and 4th bakeries (1 pleasure), visit the 4th bakery (6 pleasures), follow the road between the 4th and 2nd bakery (1 treat), visit 2nd bakery (5 treats), walk along the road between 2nd and 3rd bakeries (10 treats), visit 3rd bakery (4 treats). Total pleasure - 10+1+6+1+5+10+4 = 37.
| |
![]()
|
|
Темы:
Dynamic programming on subtrees
Caiman has an unusual dream, that he is in a strange part of the city. This area can be represented as a tree graph, where the vertices are intersections and the edges are two-way roads that connect these intersections. There are n intersections in total and each has its own number from 0 to n-1.
But not everything is so bad in this dream, because on every road between intersections with numbers u and v there are Cu,v dumplings! Caiman loves dumplings very much, so he wants to eat as much as possible, but there is a problem - if he visits any crossroads more than k times, he will be attacked by an evil dumpling monster.
Although this is a dream, the dumplings on each road can only be eaten once, although nothing prevents you from walking along the roads several times. Also Cayman does not stop on the roads. That is, if he starts to move from one intersection to another, then he will definitely go all the way to the next intersection.
At the beginning of the dream, Caiman is at the crossroad number 0. Help him determine the maximum number of dumplings he can eat without being attacked by the evil dumpling monster.
Input:
The first line contains two integers n and k (3 ≤ n ≤ 105; 1 ≤ k ≤ 105) &mdash ; the number of intersections and the maximum number of visits to each of the intersections.
The next n - 1 lines contain three integers u, v and Cu,v (0 ≤ u, v ≤ n - 1; 0 ≤ Cu,v< /sub> ≤ 10000), meaning that the intersections with numbers u and v are connected by a road with Cu,v dumplings.
It is guaranteed that intersections and roads form a tree.
Output:
Print a single integer - the maximum number of dumplings Caiman can eat.
Examples:
| Input |
Output |
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 15 |
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
| 17 |
11 6
1 0 7932
21 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
| 54092 |
Explanation:
In the first example, you need to visit intersections in the following order: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, ?2, ?8. Then he will eat a total of 1+2+2+1+3+3+3 = 15 dumplings.
Note that no intersection is visited more than 3 times.
| |
![]()
|