I just learned about the concept and decided to practise it on Codeforces since it seemed pretty straight forward.

I am getting WA on 3.

Since this is my first time implementing this algorithm, I need someone to correct my code.

I first read Centroid Decomposition of Tree but that was too long, so I compressed it a bit, keeping only a parent array instead of making a new tree like they did.

These are the functions that build the parent array(the ones I suspect wrong) :

bool Centroid[MAXN] = {0};
 
void Decomp(vector<int> graph[],int x,int parent[],int p){
// find the centroid that is either x or it's neighbour
// and assign "p" as it's parent
 
	int sz[MAXN] = {0};
	bool v[MAXN] = {0};
	
	setSize(graph,v,sz,x);
// a DFS function to compute the sizes of the subtrees rooted at the neighbours of x
// to check if they verify the condition
 
	for(auto node: graph[x]) if(sz[node] > sz[x]/2){
		Decomp(graph,node,parent,p);
		return;
	}
	
// x is the centroid
 
	parent[x] = p;
	Centroid[x] = 1;
	
	for(auto node: graph[x]) if(!Centroid[node]) Decomp(graph,node,parent,x);
}

And these are the two query functions, which I believe there's nothing wrong with :

void paint(int x,int parent[],int dist[]){
	dist[x] = 0;
	
	int i = 0;
	while(parent[x] != -1){
		++i;
		dist[parent[x]] = min(dist[parent[x]] , dist[x] + i);
		x = parent[x];
	}
}

int D(int x,int N,int parent[],int dist[]){
	int d = min(N+1,dist[x]);
	
	int i=0;
	int y = x;
	while(parent[y] != -1){
		++i;
		d = min(d,dist[parent[y]]+i);
		y = parent[y];
	}
	
	return dist[x] = d;
}

Thanks !