Help in a tree question
Chef has a rooted tree with N vertices (numbered 1 through N); vertex 1 is the root of the tree. Initially, there are some bacteria in its vertices. Let's denote the number of sons of vertex v by sv; a leaf is a vertex without sons. During each second, the following events happen:
For each non-leaf vertex v, if there are x bacteria in this vertex at the start of this second, they divide into sv⋅x bacteria. At the end of this second, x of these bacteria instantly move to each of its sons (none of them stay in vertex v). The original x bacteria do not exist any more.
Zero or more bacteria appear in one vertex. These bacteria do not divide or move at this second.
Initially, we are at the start of second 0. You should process Q queries ― one query during each of the seconds 0 through Q−1. There are two types of queries:
+ v k: During this second, k bacteria appear in vertex v.
? v: Find the number of bacteria in vertex v at the end of this second ― after the divided bacteria have moved.
Input
The first line of the input contains two space-separated integers N and Q.
Each of the next N−1 lines contains two space-separated integers x and y denoting that vertices x and y are connected by an edge.
The next line contains N space-separated integers a1,a2,…,aN denoting the initial numbers of bacteria in vertices 1 through N.
Q lines follow. Each of these lines describes a query in the format + v k or ? v.
Output
For each query of the second type, print a single line containing one integer ― the number of bacteria in the given vertex.
Constraints
1≤N,Q≤5⋅105
1≤ai≤109 for each valid i
1≤x,y≤N
the graph described on the input is a tree
1≤v≤N
1≤k≤109
Subtasks
Subtask #1 (20 points): 1≤N,Q≤5,000
Subtask #2 (30 points): 1≤N,Q≤105
Subtask #3 (50 points): original constraints
Example Input
5 8
4 3
3 1
5 2
1 2
1 10 4 9 4
+ 1 6
? 3
+ 3 5
? 3
+ 2 2
+ 5 10
? 5
? 4
Example Output
6
0
33
25
Explanation
The numbers of bacteria in all vertices at the end of each second are:
0-th second: 6,1,1,13,14
1-st second: 0,6,6,14,15
2-nd second: 0,0,5,20,21
3-rd second: 0,0,0,25,21
4-th second: 0,2,0,25,21
5-th second: 0,0,0,25,33
6-th second: 0,0,0,25,33
7-th second: 0,0,0,25,33
For each non-leaf vertex v, if there are x bacteria in this vertex at the start of this second, they divide into sv⋅x bacteria. At the end of this second, x of these bacteria instantly move to each of its sons (none of them stay in vertex v). The original x bacteria do not exist any more.
Zero or more bacteria appear in one vertex. These bacteria do not divide or move at this second.
Initially, we are at the start of second 0. You should process Q queries ― one query during each of the seconds 0 through Q−1. There are two types of queries:
+ v k: During this second, k bacteria appear in vertex v.
? v: Find the number of bacteria in vertex v at the end of this second ― after the divided bacteria have moved.
Input
The first line of the input contains two space-separated integers N and Q.
Each of the next N−1 lines contains two space-separated integers x and y denoting that vertices x and y are connected by an edge.
The next line contains N space-separated integers a1,a2,…,aN denoting the initial numbers of bacteria in vertices 1 through N.
Q lines follow. Each of these lines describes a query in the format + v k or ? v.
Output
For each query of the second type, print a single line containing one integer ― the number of bacteria in the given vertex.
Constraints
1≤N,Q≤5⋅105
1≤ai≤109 for each valid i
1≤x,y≤N
the graph described on the input is a tree
1≤v≤N
1≤k≤109
Subtasks
Subtask #1 (20 points): 1≤N,Q≤5,000
Subtask #2 (30 points): 1≤N,Q≤105
Subtask #3 (50 points): original constraints
Example Input
5 8
4 3
3 1
5 2
1 2
1 10 4 9 4
+ 1 6
? 3
+ 3 5
? 3
+ 2 2
+ 5 10
? 5
? 4
Example Output
6
0
33
25
Explanation
The numbers of bacteria in all vertices at the end of each second are:
0-th second: 6,1,1,13,14
1-st second: 0,6,6,14,15
2-nd second: 0,0,5,20,21
3-rd second: 0,0,0,25,21
4-th second: 0,2,0,25,21
5-th second: 0,0,0,25,33
6-th second: 0,0,0,25,33
7-th second: 0,0,0,25,33
The key here is to recognize that the bacteria spread in a wave from parent to child. To compute the number of bacteria at node N at time T, you need to start at the root node at time T-D where D is the depth of node N. Then run through the rules for each second as you descend the graph from the root to node N, keeping track of the total bacteria as you go.
To do this you need to store the graph. Within each node, store the number of bacteria that were added by a query (NOT the number added by the parent's bacteria spreading), and the time (second) when the bacteria appeared there. Since Chef can add bacteria to a cell several times, you'll need a collection of these.
You should also store a pointer or index to the node's parent.
When you get a + query, you add that bacteria count & timestamp to the node.
When you get a ? query, you start at cell v and recursively go up the tree, counting the depth until you get to the root. Suppose you discover that v is at depth 5. Then start at time T-5 and see if any bacteria was added to the root at that time. If so then add that to your count.
Now, as you unwind the recursion, you descend the tree back to node v. At the next second (T-4), "count" bacteria migrated to the root's child on the path. Check if Chef added any bacteria to that child at time T-4. If so, you'll need to add that number to your total count.
And then you go to the next child and do the same calculation for time T-3
and down and down to the node that was queried.
Now somethings I hate about CodeChef problems.
Let's denote Chef's sexist attitude by a raised middle finger.
And what about the leaf vertices? Chef says that the parent's bacteria spreads down to the leaf, but then what happens to it? Does it die in the next second? Does it live forever? Does it fly away on a unicorn and come back next summer? The example seems to indicate that bacteria stop at the leaf and fester there forever.
To do this you need to store the graph. Within each node, store the number of bacteria that were added by a query (NOT the number added by the parent's bacteria spreading), and the time (second) when the bacteria appeared there. Since Chef can add bacteria to a cell several times, you'll need a collection of these.
You should also store a pointer or index to the node's parent.
When you get a + query, you add that bacteria count & timestamp to the node.
When you get a ? query, you start at cell v and recursively go up the tree, counting the depth until you get to the root. Suppose you discover that v is at depth 5. Then start at time T-5 and see if any bacteria was added to the root at that time. If so then add that to your count.
Now, as you unwind the recursion, you descend the tree back to node v. At the next second (T-4), "count" bacteria migrated to the root's child on the path. Check if Chef added any bacteria to that child at time T-4. If so, you'll need to add that number to your total count.
And then you go to the next child and do the same calculation for time T-3
and down and down to the node that was queried.
Now somethings I hate about CodeChef problems.
| Let's denote the number of sons of vertex v by sv |
| For each non-leaf vertex v... |
@dhayden
Yes the bacteria stays at the leaf node. How can we calculate the? Query for leaf in less time complexity
Yes the bacteria stays at the leaf node. How can we calculate the? Query for leaf in less time complexity
can you do this with a pair (or triplet?) of alternating data structures where one is all the leaves and the other is their parents? Since parents die out every iteration?
I think you'll find that what I've proposed is very fast for "normal" cases. It will be slow if the tree is really just a linked list and/or all the bacteria is added to the same node, but otherwise it should be pretty quick - roughly n*log(n)
| But what to do in the case when D>T?? |
@dhayden
Yes the bacteria stays at the leaf node. How can we calculate the? Query for leaf in less time complexity
Yes the bacteria stays at the leaf node. How can we calculate the? Query for leaf in less time complexity
Hmm. I think as you go up the tree, and backward in time, if you're looking for the total bacteria in a leaf, it's the bacteria added to to the cell at or before the time being considered.
Topic archived. No new replies allowed.