BACREP - Editorial

Author: Mikaeel
Tester: Hanlin Ren
Editorialist: Hanlin Ren

Medium-Hard

PREREQUISITES:

Trees, Depth First Search, Segment Tree / Fenwick Tree

PROBLEM:

There is a rooted tree of N vertices, and some vertices contain bacteria. In every second:

• Every bacterium in a non-leaf vertex v splits into d copies, where d is the number of children of v.
• Then each copy goes to a distinct children.
• Bacteria at leaves doesn’t move, split or disappear.

You need to process q seconds. In the i-th second you’re required to either put k_i new bacteria to vertex v_i, or output the number of bacteria currently at the vertex v_i.

QUICK EXPLANATION:

• We process the seconds (i.e. queries) in ascending order of i-dep(v_i), where i is the time of that query, dep(v_i) is the depth of the vertex that query works on.
• We maintain two copies T_{\sf leaf},T_{\sf nonleaf} of the input tree, one for leaf queries and one for non-leaf queries.
• For each query "+ v_i k_i", add value k_i to every node in the subtree of v_i (in both trees).
• For each query "? v_i", if v_i is a leaf, output the value of v_i in T_{\sf leaf}, otherwise output the value of v_i in T_{\sf nonleaf}.
• Recall that we iterate through the queries by nondecreasing order of i-dep(v_i). Whenever this number changes (i.e. increases), clear all values in T_{\sf nonleaf}.

EXPLANATION:

Notation: let’s denote the operation in the i-th second be either "+ v_i k_i", or "? v_i". That is, v_i is always the vertex operated in the i-th second, and k_i is the number of bacteria added to v_i if in the i-th second we put bacteria in v_i.

We start with an observation. Consider a bacterium which is at vertex v in the i-th second. As it (technically, one of its copies) goes down the tree, if it hasn’t reached a leaf node, then the difference between its depth and the time doesn’t change. In other words, if it’s at vertex u in the j-th second (and u is not a leaf), then i-dep(v)=j-dep(u). The proof is simple: each second its depth increases by 1. Given this observation, the following definition may be useful. For the query in the i-th second, let’s denote E[i]=i-dep(v_i).

Let’s consider the i-th query and suppose it is of the form "? v_i". There are two cases.

Case 1: v_i is not a leaf. Consider all queries of the form "+ v_j k_j". This query contributes to the i-th query, if and only if the following two conditions hold:

• E[j]=E[i], i.e. j-dep(v_j)=i-dep(v_i);
• v_j is an ancestor of v_i.

(We may want a third condition that j<i as well, but that’s already implied by the above two conditions.)

Therefore, we group these q seconds by their E[\cdot] values. For each group (with the same E[\cdot] value), the problem becomes:

• For each query of the form "+ v_j k_j", simply add k_j bacteria to the node v_j;
• For each query of the form "? v_j", output the total number of bacteria in the ancestors of v_j.

(Note that in this case, queries in different groups does not influence each other.)

Or equivalently:

• For each query of the form "+ v_j k_j", adds k_j bacteria to every node in the subtree of v_j;
• For each query of the form "? v_j", output the number of bacteria in the vertex v_j.

This is a very standard data structure problem on trees, and by using segment trees or Fenwick trees to maintain the DFS order, we can solve the problem in O((n+q)\log n) time.

First, we need to compute the DFS order of a tree. The DFS order is the order of nodes that we encounter during a Depth-first search, and it can be computed by the following pseudocode:

DFS(x)
push vertex x to the DFS order
for (v in children of x)
DFS(v)


For example, a possible DFS order of the tree below is (1,2,12,6,13,7,10,9,3,4,11,5,14,8).

A good property of DFS order we will use is that, every subtree corresponds to an interval of the DFS order. For example, the subtree of vertex 2 corresponds to the interval (1,{\bf\color{red} 2,12,6,13,7,10,9,3},4,11,5,14,8), and the subtree of vertex 11 corresponds to the interval (1,2,12,6,13,7,10,9,3,4,{\bf\color{red}11,5,14},8).

Let [l[i],r[i]] be the interval corresponding to the subtree of the i-th vertex. In the above example l[2]=2, r[2]=9, l[11]=11, r[11]=13. To compute l[i],r[i], we maintain the number of visited vertices in our DFS algorithm. Whenever we enter x, l[x] is the number of visited vertices; whenever we leave x (so we’ve processed the subtree of x), r[x] is (also) the number of visited vertices.

global variable num_of_visited_vertices
DFS(x)
push vertex x to the DFS order
num_of_visited_vertices++
l[x] = num_of_visited_vertices
for (v in children of x)
DFS(v)
r[x] = num_of_visited_vertices


Now we maintain an array A[1\sim n] and process the queries. Let DFS[i] be the i-th node in the DFS order, initially A[i] is the number of initial bacteria in vertex DFS[i]. When we add k_j bacteria to the subtree of v_j, we add k_j to the every element in the segment A[l[v_j],r[v_j]]. When we query about the number of bacteria in vertex v_j, we output A[l[v_j]]. (Note: by the above algorithm we can see that v_j is the l[v_j]-th vertex in the DFS order. Therefore the number of bacteria on v_j is stored in A[l[v_j]].)

The problem becomes the following (really) classical problem: given an array, support range addition and point query. We can solve this problem by segment trees or Fenwick trees.

Case 2: v_i is a leaf. The situation is very similar. A modification + v_j k_j contributes to the query ? v_i, if and only if the following two conditions hold:

• E[j]\le E[i], i.e. j-dep(v_j)\le i-dep(v_i);
• v_j is an ancestor of v_i.

(Note that j<i still follows from the above conditions.)

We sort the q seconds by ascending order of E[\cdot], then iterate through them. If the current second is a modification + v_j k_j, we add k_j bacteria to every vertex in the subtree of v_j. If it’s a query ? v_j, we output the number of bacteria in v_j. We can still use the aforementioned DFS-order based solution. The time complexity is still O((n+q)\log n).

Implementation Details. We can actually solve Case 1 and Case 2 simultaneously.

• We maintain two segment trees (or Fenwick trees if you like), one for Case 1 and one for Case 2.
• We still visit all operations by ascending order of E[\cdot]. Each time we meet a modification (query resp), we perform a subtree addition (point evaluation resp).
• When the E value of the current operation changes (i.e. increases), it means that we reached a new group of operation (in Case 1). Therefore we clear the first segment tree, and proceed as usual.
• To clean a segment tree, we can’t iterate through all its nodes, since otherwise the time complexity degenerates to O(nq). Instead, we undo the operations that we did in the last group.
• The time complexity is still O((n+q)\log n).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
#define put(x) cout<<#x<<" = "<<x<<endl;
using namespace std;
const int maxn=2e6+10,maxq=4e6+10;

struct Query{
int id,time,v,k;
char type;
Query(){}
Query(int _id,char _type,int _time,int _v,int _k=0,long long _answer=0){
id=_id;
type=_type;
time=_time;
v=_v;
k=_k;
}
};

int n,q,H[maxn];
int qsize=0,startingTime[maxn],finishingTime[maxn],curTime=0;
long long A[maxn];
bool isLeaf[maxn];
vector<int> G[maxn];
Query Q[maxq];
int Qper[maxq];

void dfs(int a,int par=-1){
startingTime[a]=curTime++;
for(int b:G[a]){
if(b!=par){
H[b]=H[a]+1;
dfs(b,a);
}
}
if(int(G[a].size())-(par!=-1)==0){
isLeaf[a]=1;
}
finishingTime[a]=curTime;
}

struct FenwickTree{
long long s[maxn];
bool mark[maxn];
int history[maxn],historySize=0;
x+=5;
if(!mark[x]){
mark[x]=1;
history[historySize++]=x;
}
for(int i=x;i<maxn;i+=i&-i){
s[i]+=value;
}
}

// [L,R)
void add(int L,int R,long long value){
}

x+=5;
long long ans=0;
for(int i=x;i>0;i-=i&-i){
ans+=s[i];
}
return ans;
}

void clear(){
for(int i=0;i<historySize;i++){
int a=history[i];
mark[a]=0;
for(int j=a;j<maxn;j+=j&-j){
s[j]=0;
}
}
historySize=0;
}
}fenwick[2];

int32_t main(){
scanf("%d%d",&n,&q);
for(int i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
a--,b--;
G[a].push_back(b);
G[b].push_back(a);
}
dfs(0);
for(int i=0;i<n;i++){
scanf("%d",A+i);
// this query doesn't need to have a valid id
}
for(int i=1;i<=q;i++){
Q[qsize].id=i;
scanf(" %c",&Q[qsize].type);
scanf("%d",&Q[qsize].v);
Q[qsize].v--;
Q[qsize].time=i-H[Q[qsize].v];
scanf("%d%d",&Q[qsize].v,&Q[qsize].k);
Q[qsize].v--;
Q[qsize].time=i-H[Q[qsize].v];
}else{
assert(0);
}
qsize++;
}
for(int i=0;i<qsize;i++){
Qper[i]=i;
}
sort(Qper,Qper+qsize,[](int a,int b){
if(Q[a].time!=Q[b].time){
return Q[a].time<Q[b].time;
}
// For queries with the same time, addQuery has more priority
return Q[a].type=='+' && Q[b].type=='?';
});
for(int i=0;i<qsize;i++){
if(i>0 && Q[Qper[i-1]].time!=Q[Qper[i]].time){
fenwick[1].clear();
}
}
int fenwickId=1;
if(isLeaf[Q[Qper[i]].v]){
fenwickId=0;
}
}
}
for(int i=0;i<qsize;i++){
}
}
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;

#define sz 500200
#define next nnext
#define sum ssum
typedef long long ll;

template <class Q> void gi(Q &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
template <class Q> void pi(Q x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}
char gc() {char ch = getchar(); while (ch != '+' && ch != '?') ch = getchar(); return ch;}

int n, q;
int node[sz], next[sz << 1], to[sz << 1], e;
void ins(int x, int y) {e++; next[e] = node[x]; node[x] = e; to[e] = y;}
int dep[sz], par[sz];
bool isleaf[sz];
int seq[sz], I, st[sz], ed[sz];

void dfs(int x, int p) {
seq[st[x] = ++I] = x;
for (int j = node[x]; j; j = next[j])
if (to[j] != p) {
par[to[j]] = x; dep[to[j]] = dep[x] + 1; isleaf[x] = 0;
dfs(to[j], x);
}
ed[x] = I;
}

void init() {
int i, u, v, k;
gi(n); gi(q);
for (i = 1; i < n; i++) {
gi(u); gi(v);
ins(u, v); ins(v, u);
}
for (i = 1; i <= n; i++) isleaf[i] = 1;
dfs(1, -1);
}

char qc[sz << 1];
int qv[sz << 1], qk[sz << 1];
int qtm[sz << 1], next2[sz << 1], to2[sz << 1], e2;
void ins2(int x, int y) {e2++; next2[e2] = qtm[x]; qtm[x] = e2; to2[e2] = y;}

ll a1[sz], a2[sz], ans[sz];
void add(ll *a, int x, int y) {for (; x <= n; x += x & -x) a[x] += y;}
ll sum(ll *a, int x) {ll s = 0; for (; x; x -= x & -x) s += a[x]; return s;}

void query() {
int i, j, k;
for (i = 1; i <= n; i++) {
qc[i] = '+'; qv[i] = i; gi(qk[i]);
ins2(n - dep[i], i);
}
for (i = 1; i <= q; i++) {
qc[j = i + n] = gc();
if (qc[j] == '+') gi(qv[j]), gi(qk[j]);
else gi(qv[j]);
ins2(n + i - dep[qv[j]], j);
}
for (i = 1; i <= n + q; i++) {
for (j = qtm[i]; j; j = next2[j]) {
k = to2[j];
if (qc[k] == '+')
}
for (j = qtm[i]; j; j = next2[j]) {
k = to2[j];
if (qc[k] == '?') {
if (isleaf[qv[k]]) ans[k - n] = sum(a2, st[qv[k]]);
else ans[k - n] = sum(a1, st[qv[k]]);
}
}
for (j = qtm[i]; j; j = next2[j]) {
k = to2[j];
if (qc[k] == '+') ADD(a1, st[qv[k]], ed[qv[k]], -qk[k]);
}
}
for (i = 1; i <= q; i++)
if (qc[i + n] == '?') pi(ans[i]), putchar('\n');
}

int main() {init(); query(); return 0;}

18 Likes

Going to link - for the last time, honest! - to my commented solution, here

21 Likes

Given the efforts you spend in documentation of the code, you shouldn’t be shy to share that link again and again.

14 Likes

Let’s assume we had no updates, so answer to any query at time t on non-leaf vertex u will be the original value of that vertex v which is reached after moving t steps above u, and for a leaf vertex u, it will be sum of values of vertices on path from u to v.
Actually updates on a vertex u are needed to be handled in a similar way. But this way some updates can wrongly affect other queries. So there’s a need to do updates, then do some queries and then undo the updates.
So what’s the right order to handle queries and updates? After scratching your head a bit you will realize that dfs order serves this exact purpose.

For moving up the tree we can use binary lifting technique.
And for path sum queries we can use inclusion-exclusion by keeping two segment trees, both based on euler tours, one which stores entry values and other which stores exit values.
Also we need to add a path tree of q (No. of queries) nodes at top of root of the original tree.

https://www.codechef.com/viewsolution/27365890

Hence final complexity O((N + Q)logN).

4 Likes

I just used time - depth[v] as index of array and build the sum segment tree over it. Then just process the query based on nodes in DFS traversal order. Since at any time segment tree contains updates of the all ancestor of any node, hence query reduced to sum of 0-L for leaf nodes and L-L for non-leaf nodes . So it is like :

1. On reaching any node n, add all updates queries of node n.
2. Process all the answer queries for node n
3. Recursively traverse all the children
4. Once all children are processed then remove all the updates of the node n from the segment tree.
5 Likes

@r_64 how to solve this question online. is it possible to use link cut tree here.

I am not able to understand how we are handling subtree updates and point queries in case of leaf nodes.

In the leaf case, the problem is also reduced to “subtree updates, point queries” in a tree. We can use the same method (as in my spoiler tag) to solve the “subtree updates, point queries” problem.

(That means we need to solve two “subtree updates, point queries”'s, one for leaf and one for non-leaf. The two problems use the same algorithm.)

3 Likes

@r_64 and @ssjgz amazing editorials both of you!

1 Like

Just by maintaining an extra chain of nodes of length q above the root node and updating the node which is at (depth - time) times above it will be sufficient (this way we always have a node whom we can update). For a non-leaf node, the value of the respective parent at (depth - time) is the answer and for a leaf node sum of all nodes in the path from leaf to node from (depth - time) is the answer. We can solve this online.

I doubt that it can be solved online this way!
The queries need to be processed in the dfs style else what you update going upwards will affect wrongly queries on other sub trees as well (since you are going up you have no control over which subtree the update was intended for and which subtrees actually query it).
Or may be I’m missing out something. Please clarify!

3 Likes

How will you know when to undo the updates if the queries are coming online?

Can Anybody Tell why in author implementation, in "add " function of fenwick tree, x += 5 is done?

@vijju123
I understand that initial bateria at node at depth d can be understood as some sort of an update performed at -d seconds at root, which can descended now on current node.

I understand how time minus depth plays a key role in adding up of bacteria descended.

I am still unable to understand how the above concepts fit into a segment array. The only thing I understand about segment tree is that it can update and query a range of locations.

Help me to fill in the vital information, please!

Edit: In the editorial example, if I look at node 11, all its ancestors - i.e. 1 and 4 occur to the left of 11 in the DFS.

@dardev If you look at the DFS order, you will find that every subtree in the original tree, is a continuous range or subarray of it. So, since update at a node would affect all nodes in its subtree, update is equivalent to range update (range corresponding to subtree). The range for updates on subtrees of 1 and 4 in this example will include 11 since it is in the subtree. Later when you query for 11, you will find sum of all previous updates on any of its ancestors.

2 Likes

Thank you for the reply @hemanth_1

I understand that we are doing DFS from root.
So - first I need to think in terms of a function that returns subtree for given node as a query?

I am unable to understand how to store queries and how to arrange the queries accordingly i.e. by i - dep(v), please help me to understand this…