Centroid Decomposition on a tree(Beginner)

Revision en8, by YoyOyoYOy000y000, 2021-01-14 19:29:39

## When Centroid Decomposition comes?

1. Suppose a problem says that how many paths have a length exactly k in a tree.
2. Or, how many paths have xor k.
3. Sum of all xor path in a tree.
4. update a node Black to white or white to black. now query the shortest path from a node to a white node. etc.

So, it is clear, when a paths problem comes then we can use Centroid Decomposition.

For a single node query or from a specific node, DSU on Tree may do it.

## Algorithm:

### 1. Find a centroid of current tree T.

What is Centroid?

Simply Centroid is a node if we delete it. It makes some subtrees where every subtree size must be less than sz/2 { sz is the size of the current tree T.}

How can we find it?

=> Take a node random node of current tree T. Now if it's every subtree size less than sz/2. Then it is a centroid. => If not, go to the highest size of the subtree.

Note: In a tree only two Centroid possible From Jordan Theorem. If there are two centroids. you can take any. Cause those two centroids to look like the same

=> Same thing must be done.

In this graph. If we start from node 1. Then Size=7 which is larger than 11/2. so 1 is not centroid. Go to the 2. Now every subtree size less than 11/2. So for this graph centroid is 2. Here is the code for finding the centroid of the current Tree.

/// 'u' will give us the centroid
int u = _u;
while (true) {
int nu = -1;
for (int v : e[u]) {
if (!tocheck[v] || v == p[u]) continue;
if (1 + size[v] > sz / 2) nu = v;
}
if (sz &mdash; 1 &mdash; size[u] > sz / 2 && p[u] != -1
&&tocheck[p[u]]) nu = p[u];
if (nu != -1) u = nu; else break;
}
/// tocheck array check whether this node is already done as a centroid of any tree or not

/// For size array you need just a dfs call
void dfs(int u) {
for (int v : e[u]) {
if (v == p[u]) continue;
p[v] = u;
dfs(v);
size[u] += 1 + size[v];
}
}


### 2. Problem-Solving part.

Before Deleting centroid. we must find the answer for the current Tree T.

**You must solve this part with O(sz) time**

suppose we need to find how many paths length equal k. Then we need to compute for current tree T.

**how many paths go through the centroid of T which length equal k?**

Take your time and think about it. If we call a dfs from the centroid node and find the length of all nodes from the centroid, then it will be easier for us.

void dfs2(int u,int p,int val,bool flag)
{
if(flag) cnt[val]++;
else cnt[val]--;
for(auto v : e[u])
{
if(tocheck[v] && v!=p)
{
dfs2(v,u,val+1,flag);
}
}

}
void solve(int u,int p,int val)
{
if(val>k) return ;
sol+=cnt[k-val];
for(auto v : e[u])
{
if(tocheck[v] && v!=p)
{
solve(v,u,val+1);
}
}
}
void func(int u,int par)
{
sol=0;
dfs2(u,par,0,1);
sol+=cnt[k];
for(auto X : e[u])
{
if(tocheck[X])
{
dfs2(X,u,1,0);
solve(X,u,1);
dfs2(X,u,1,1);
}
}
ans+=sol/2;
}


### 3. Delete the Centroid node C and find the new centroid of all subtrees. ### 4. Repeat the same Thing from 1 to 3 for every subtree. ## Property:

1. The main property here is every node comes logn times under a centroid. So total complexity NlogN .
2. Any path property like distance/xor/sum/etc. we can compute (logn+logn)times. Cause Highest depth for the centroid Tree is logn.
3. LCA of any two nodes in centroid tree logn.

Full Code is here for finding all path length equal to k

#define ll              long long
#define vi              vector<int >
#define vil             vector<ll >
#define pb              push_back
#define fi              first
#define sc              second
#define pii             pair<int , int >

const int N   = 500050;
const int INF = 1e9+100;
ll sol,k,ans;
struct CentroidDecomposition {
/// cd for Centroid Tree
/// e for Main tree
vector<vi> cd, &e;
/// tocheck for checking a node is already in centroid tree or not?
vector<bool> tocheck;
/// p for tracking parent of a node
/// cnt for counting length
vi size, p,cnt;
/// centroid Tree root
int root;
CentroidDecomposition(vector<vi> &tree) : e(tree) {
int sz = e.size();
tocheck.assign(sz, true);
col.assign(sz, false);
cd.assign(sz, vi());
p.assign(sz, -1);
cnt.assign(N, 0);
size.assign(sz, 0);
dfs(0);
root = decompose(0, sz,-1);
}
void dfs(int u) {
for (int v : e[u]) {
if (v == p[u]) continue;
p[v] = u;
dfs(v);
size[u] += 1 + size[v];
}
}
/// we can solve it for any amount of k
void dfs2(int u,int p,int val,bool flag)
{
if(flag) cnt[val]++;
else cnt[val]--;
for(auto v : e[u])
{
if(tocheck[v] && v!=p)
{
dfs2(v,u,val+1,flag);
}
}

}
void solve(int u,int p,int val)
{
if(val>k) return ;
sol+=cnt[k-val];
for(auto v : e[u])
{
if(tocheck[v] && v!=p)
{
solve(v,u,val+1);
}
}
}
/// finiding centroid and get answer for this centroid
int decompose(int _u, int sz,int par) {
int u = _u;
while (true) {
int nu = -1;
for (int v : e[u]) {
if (!tocheck[v] || v == p[u]) continue;
if (1 + size[v] > sz / 2) nu = v;
}
if (sz - 1 - size[u] > sz / 2 && p[u] != -1
&&tocheck[p[u]]) nu = p[u];
if (nu != -1) u = nu; else break;
}
for (int v = p[u]; v != -1 && tocheck[v]; v = p[v])
size[v] -= 1 + size[u];
sol=0;
dfs2(u,par,0,1);
sol+=cnt[k];
for(auto X : e[u])
{
if(tocheck[X])
{
dfs2(X,u,1,0);
solve(X,u,1);
dfs2(X,u,1,1);
}
}
ans+=sol/2;
dfs2(u,par,0,0);
tocheck[u] = false;
for (int v : e[u]) {
if (!tocheck[v]) continue;
int V2 = 1 + size[v];
if (v == p[u]) V2 = sz - 1 - size[u];
cd[u].push_back(decompose(v, V2,u));
}
return u;
}
};

int main(){
int n;
cin >> n>>k;
vector<vi> tree(n, vi());
for (int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
a--; b--;
tree[a].push_back(b);
tree[b].push_back(a);
}
CentroidDecomposition cd(tree);
cout<<ans<<endl;
return 0;
}


You can find different type of code here Path problem and normal centroid implementation

** More problem **

You can also check this blog

Centroid Decomposition of a Tree by Tanuj Khattar

Sorry for the bad grammatical issues.

Thank You #### History

Revisions Rev. Lang. By When Δ Comment
en8 YoyOyoYOy000y000 2021-01-14 19:29:39 489
en7 YoyOyoYOy000y000 2020-02-08 00:17:03 86
en6 YoyOyoYOy000y000 2020-02-08 00:13:46 452
en5 YoyOyoYOy000y000 2020-02-07 21:50:23 4 Tiny change: 'ree . **\n~~~~~\n\' -> 'ree . **\n\n~~~~~\n\'
en4 YoyOyoYOy000y000 2020-02-07 21:48:30 126
en3 YoyOyoYOy000y000 2020-02-07 20:55:49 4 Tiny change: 'tree only one Centroid ' -> 'tree only two Centroid '
en2 YoyOyoYOy000y000 2020-02-07 19:37:51 346 Tiny change: 'ng part.\n Be' -> 'ng part.\n\n Be'
en1 YoyOyoYOy000y000 2020-02-07 19:14:57 7352 Initial revision (published)