### qmk's blog

By qmk, 5 years ago,

Original post : [Tutorial] Sack (dsu on tree)

In this post, I am trying to explain every line of dsu on tree code.

The reason is the same as blog 51139 when I first learn it.

How many vertices in the subtree of vertex v has some property in $O(n \ log \ n)$ time (for all of the queries)?

For example:

Given a tree, every vertex has a color. The query is how many vertices in the subtree of vertex v are colored with color c?

First, calculate the size of the subtree of every vertex, it can be done with a single dfs $(sz[v] = v + all(sz[child \ of \ v]))$

void dfs_size(int v, int p) {
sz[v] = 1;
for (auto u : adj[v]) {
if (u != p) {
dfs_size(u, v);
sz[v] += sz[u];
}
}
}


Code:

void dfs(int v, int p, bool keep) {
int Max = -1, bigchild = -1;
for (auto u : adj[v]) {
if (u != p && Max < sz[u]) {
Max = sz[u];
bigchild = u;
}
}
for (auto u : adj[v]) {
if (u != p && u != bigchild) {
dfs(u, v, 0);
}
}
if (bigchild != -1) {
dfs(bigchild, v, 1);
swap(vec[v], vec[bigchild]);
}
vec[v].push_back(v);
cnt[color[v]]++;
for (auto u : adj[v]) {
if (u != p && u != bigchild) {
for (auto x : vec[u]) {
cnt[color[x]]++;
vec[v].push_back(x);
}
}
}
// there are cnt[c] vertex in subtree v color with c
if (keep == 0) {
for (auto u : vec[v]) {
cnt[color[u]]--;
}
}
}


Explanation :

$cnt[c]$ in $dfs(v)$ will be answered for query in vertex v with the color c

each time we do dfs in the subtree of v, we will keep all nodes in the subtree of v in $vec[v]$,

update information (color count for each node) from subtree child while adding a node to $vec[v]$.

boolean keep denote if we are working on the subtree of $bigchild \ (keep = 1)$ or $smallchild \ (keep = 0)$

void dfs(int v, int p, bool keep)


let say we are at subtree v

int Max = -1, bigchild = -1;
for (auto u : adj[v]) {
if (u != p && Max < sz[u]) {
Max = sz[u];
bigchild = u;
}
}


First, we will find a big child using pre-calc $sz[u]$.

Note that the big child of vertex v is the child with max subtree size

for (auto u : adj[v]) {
if (u != p && u != bigchild) {
dfs(u, v, 0);
}
}

if (bigchild != -1) {
dfs(bigchild, v, 1);
swap(vec[v], vec[bigchild]);
}


then call recur for small child $(keep = 0)$ then big child $(keep = 1)$

then : $vec[v] = vec[big \ child] + v + all(vec[small \ child])$

obviously, $vec[big \ child]$ and $vec[small \ child]$ are calculated before

because we only care about current subtree, we can swap $vector[big \ child]$ and $vector[v]$

so that $vector[v]$ have bigchild information. The complexity of swap vector is $O(1)$

and current cnt array contain only bigchild information (read $if(keep == 0)$ explain part below)

$vec[v] = vec[big \ child]$

vec[v].push_back(v);
cnt[color[v]]++;


next, add information of vertex v.

$vec[v] = vec[big \ child] + v$

for (auto u : adj[v]) {
if (u != p && u != bigchild) {
for (auto x : vec[u]) {
cnt[color[x]]++;
vec[v].push_back(x);
}
}
}


$vec[v] = vec[big \ child] + v + all(vec[small \ child])$

now that $vec[v]$ is full fill, add small child to $vec[v]$ and update cnt array also

(keep in mind that bigchild information didn't get deleted so that we only need to add small child)

if (keep == 0) {
for (auto u : vec[v]) {
cnt[color[u]]--;
}
}


go down to small child, we have to delete its information about color count so that

the query answer of v's first child subtree won't affect second and so on. (because we are using global array)

That is also the reason why we have to call small child before big child recur

(to make bigchild and small child answer not overlap)

Note:

cnt is a global array

we process small child first clear them from the global array, solve big child then add all small child again

Because some problems like count distinct values in subtree can't be solved if we have a contribution

from other nodes when we are at some node only it's subtree children data must be in the global array

we need to have separate information for big and small children.

we can't just work in a single entity because of the time complexity otherwise it will be $O(n^2)$, see prove below

Complexity?

for (auto u : adj[v]) {
if (u != p && u != bigchild) {
for (auto x : vec[u]) {
cnt[color[x]]++;
vec[v].push_back(x);
}
}
}


add small child took $O(n \ log \ n)$ overall. why?

let call $y = vec[big \ child].size, \ x = vec[small \ child].size \ (y \geq x)$

let consider a vertex u $(1 \leq u \leq n)$

merge it to the bigger child so the size of vec[] of the subtree contain u

becomes $x + y \geq x + x = 2x$. So each time we merge to parent subtree

the size increase at least twice when adding and total size is only n so

we cannot add a node more than $log(n)$ time

we have n vertex u so the complexity becomes $O(n \ log \ n)$

if (keep == 0) {
for (auto u : vec[v]) {
cnt[color[u]]--;
}
}


because we only deleting information of subtree when $keep = 0$ (small subtree)

which is the same as when we add it (now delete instead of add) so the complexity is $O(n \ log \ n)$

so overall complexity is $O(n \ log \ n)$

Example:

solution

Practice:

visit original blog :>

• +100

| Write comment?
 » 5 years ago, # | ← Rev. 2 →   0 I have a doubt in the code's given by Arpa Blog, in HLD style the add function seems like it doesn't go through the whole tree if keep==0 like add function is avoiding big child for every node . he uses add function to delete elements contribution. How is this deleting properly the contribution from light/small subtrees? int cnt[maxn]; bool big[maxn]; void add(int v, int p, int x){ cnt[ col[v] ] += x; for(auto u: g[v]) if(u != p && !big[u]) add(u, v, x) } normally it should go through whole subtree of v and delete them right ?
•  » » 5 years ago, # ^ |   +35 because there is if(u != p && !big[u])
•  » » » 5 years ago, # ^ |   0 yeh, I didn't read the code properly it does the same thing ,it just avoids the immediate bigChild and traverses through rest of them , I didn't see the bigChild is cleared immediately .
•  » » » 5 years ago, # ^ |   +27 I love you UNoobAble. Do you want to be my gay partner ?
•  » » » » 5 years ago, # ^ |   +12 uwu
•  » » » » » 5 years ago, # ^ |   +19 uwu
•  » » » » » » 5 years ago, # ^ |   -6 uwu
•  » » » » » » » 5 years ago, # ^ |   -6 uwu
•  » » » » » » » » 5 years ago, # ^ |   -6 uwu
•  » » » » » » » » » 5 years ago, # ^ |   +2 owo
•  » » » » » » » » » 5 years ago, # ^ |   0 owo orz
 » 5 years ago, # |   0 Why do we need to have separate information for big and small children. Why cant we just work in a single entity.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +37 we can't just work in a single entity because of the time complexity need to be $O(n \ log \ n)$ otherwise it will be $O(n^2)$
•  » » » 5 years ago, # ^ |   0 But how big child is helping us reducing the time complexity, can you explain this a bit more.
•  » » » » 5 years ago, # ^ | ← Rev. 5 →   +28 because we process small child first clear them from the global array, solve big child then add all small child againso we just have to make $vec[v] = vec[big \ child]$ which is $O(1)$then add v, small child took $O(n \ log \ n)$ overall. why?let call $y = vec[big \ child].size, \ x = vec[small \ child].size \ (y \geq x)$let consider a vertex u $(1 \leq u \leq n)$merge it to the bigger child so the size of $vec[]$ of subtree contain u becomes $x + y \geq x + x = 2x$. So each time we merge to parent subtree the size increase at least twice when adding and total size is only n sowe cannot add a node more than $log(n)$ timewe have n vertex u so total complexity become $O(n \ log \ n)$deleting information of small subtree (at the very end of the code) is the same as when we add it sothe complexity is $O(n \ log \ n) + O(n \ log \ n)$
 » 5 years ago, # |   0 Why we r deleting the information for small child. Can u explain it more.
•  » » 5 years ago, # ^ |   +29 because we process small child first clear them from the global array, solve big child then add all small child again
 » 5 years ago, # |   0 Also from small child and big child nodes and its subtree what we r getting. Can u give a more clearer picture of it.
•  » » 5 years ago, # ^ |   +24 we get full information about the current subtree
 » 5 years ago, # |   +19 Auto comment: topic has been updated by qmk (previous revision, new revision, compare).
 » 5 years ago, # | ← Rev. 2 →   0 Ignore
 » 5 years ago, # |   +3 May I marry you uwu you are my husbando now
 » 5 years ago, # |   0 you can see more techniques and problems here.
•  » » 5 years ago, # ^ |   +16 I included the link as the original blog
•  » » » 5 years ago, # ^ |   0 OK
 » 4 years ago, # |   +8 thanks man, u r really awesome
 » 4 years ago, # |   0 Can you please explain the purpose of "keep" ?
•  » » 4 years ago, # ^ |   0 if keep = 1 then you keep information of the current vertex as its parent will use its informationif keep = 0 then your parent don't need you you have to erase your dataI suggest you thinking hard about this, it is very hard to explain it clearly, but once you understand it after hours of thinking, it will stick with you and it won't be a black box
 » 3 years ago, # |   0 why the space complexity is not n**2 ? I don't understand the * in vector *vec[maxn].
 » 5 months ago, # |   0 thanks a lot，this is the best tutorial I have ever seen
 » 3 weeks ago, # |   0 258786467 Can anybody help me, where I am doing wrong in this code? 600E - Lomsat gelral Problem