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 parentint 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 conditionfor(auto node: graph[x]) if(sz[node] > sz[x]/2){Decomp(graph,node,parent,p);return;}// x is the centroidparent[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 !