YoyOyoYOy000y000's blog

By YoyOyoYOy000y000, history, 13 months ago, In English

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[2]=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 — 1 — 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 **

  1. Distance in Tree

  2. Xenia and Tree

  3. Qtree5

  4. PrimeDist

  5. Ciel the Commander

  6. Freezing with Style

  7. Digit Tree

  8. Close Vertices

  9. Sherlock's bet to Moriarty

  10. Red-Black Cobweb

You can also check this blog

Centroid Decomposition of a Tree by Tanuj Khattar

Sorry for the bad grammatical issues.

Thank You

Read more »

 
 
 
 
  • Vote: I like it
  • +133
  • Vote: I do not like it

By YoyOyoYOy000y000, history, 13 months ago, In English

you will be given an array. and q query. q and n all less than 100000.

In every query you will be given a k. how many subarray xor less than k?

** I think it can be solved by persistent trie. but i need another solution.

Read more »

 
 
 
 
  • Vote: I like it
  • +14
  • Vote: I do not like it

By YoyOyoYOy000y000, history, 3 years ago, In English

1st we have a array of n element.

There are two types of query.

  1. 1<=r<=l<=n and D. 1<=D<=10^9 we have to add D between r to l.

  2. 1<=r<=l<=n and X. 1<=D<=10^9 .how many numbers are divisible D in r to l?

How to build segment tree for this ques.

Read more »

 
 
 
 
  • Vote: I like it
  • +17
  • Vote: I do not like it

By YoyOyoYOy000y000, history, 3 years ago, In English

which primes are best for hashing a graph? like two tree is isomorpic? then we need to hash the graph..need some prime. which are best for it. thank you :)

Read more »

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

By YoyOyoYOy000y000, history, 3 years ago, In English

hi, i think all of divisors of n(1 to 10^18) with in 9 sec is quit immpossible. if any idea or solution.please share it :) thank you

Read more »

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it