temp.md

gistfile1.md

Volunteer deployment

There are n venues (starting from 0), and the distribution of roads between venues is recorded in a two-dimensional array edges, edges[i]= [x, y] means that the i-th road connects venue x and venue y (i.e., two venues are adjacent to each other). Initially, each venue has a certain number of volunteers (the number of volunteers may vary from venue to venue), and the number of volunteers will be deployed every day for the next m days according to the popularity of the event. There are three deployment options:

1. Halve the number of volunteers in the venue with idx number.
   cnt[idx] = cnt[idx]/2;
2. Adding the number of volunteers from the venue with idx to the number of volunteers from the venue with idx in the adjacent venues. cnt[idx-1] += cnt[idx]; cnt[idx+1] += cnt[idx];
3. Subtracting the number of volunteers in the venue numbered idx from the number of volunteers in the venue numbered idx from the number of volunteers in the venue adjacent to the venue numbered idx. cnt[idx-1] -= cnt[idx]; cnt[idx+1] -= cnt[idx];

All the deployment information is recorded in the array plans, and plans[i] = [num,idx] means that the num-th deployment plan were executed for the venue with idx on the i-th day.

When reviewing the deployment plan after the event, the final number of volunteers at venue 0 is lost, and only the initial total number of volunteers at all venues totalNum, and the one-dimensional array finalCount, which records the final number of volunteers at venues 1 to n-1, are kept. Return a list of the number of volunteers.

Notes.

• The test data guarantees that when a venue makes the first deployment, the number of volunteers in that venue must be an even number.
• The test data guarantees that when the third deployment is made at a venue, the number of volunteers in adjacent venues at that venue is not negative.
• The test data guarantees that the number of volunteers in each venue at the start of a event does not exceed 10^9
• The test data guarantees that there will be no self-loops or duplicated edges in the distribution of roads between the given venues.

Example 1

input:

finalCount = [1,16]; 
totalNum = 21;
edges = [[0,1],[1,2]]; 
plans = [[2,1],[1,0],[3,0]];

output:

[5,7,9]

explanation:

	venue 0	venue 1	venue 2	Total
Initial	5	7	9	21
0-th day, venue1, plan 2	12	7	16
1-st day, venue0, plan 1	6	7	16
2-nd day, venue0, plan 3	6	1	16

Example 2

Input：

finalCnt = [4,13,4,3,8];
totalNum = 54; 
edges = [[0,3],[1,3],[4,3],[2,3],[2,5]]; 
plans = [[1,1],[3,3],[2,5],[1,0]];

Output:

[10,16,9,4,7,8]

Tips

• 2 <= n <= 5*10^4
• 1 <= edges.length <= min((n * (n - 1)) / 2, 5*10^4)
• 0 <= edges[i][0], edges[i][1] < n
• 1 <= plans.length <= 10
• 1 <= plans[i][0] <=3
• 0 <= plans[i][1] < n
• finalCnt.length = n-1
• 0 <= finalCnt[i] < 10^9
• 0 <= totalNum < 5*10^13