centroid_descomposition.cpp

int times = 0;
int L[N], R[N], sz[N];
bool S1[N], S2[N];
int ans[N], p[N];

void dfs(int x, int p){
    L[x] = times++;
    for(int v : adj[x])
      if(v != p) dfs(v, x);
    R[x] = times++;
}

int dfsz(int x){
  sz[x] = S1[x] = 1;
  for(int v : adj[x])
    if(not S1[v] and not S2[v])
      sz[x] += dfsz(v);
  return sz[x];
}

int centroid(int x, int nx){
  int maxisz = nx - sz[x];
  int Centroid = -1;
  S1[x] = 0;
  for(int v : adj[x])
    if(S1[v] and not S2[v]){
      maxisz = max(maxisz, sz[v]);
      Centroid = max(Centroid, centroid(v, nx));
    }
  
  return 2*maxisz <= nx ? x : Centroid;
}

int centroid_descomposition(int x){
  int Centroid = centroid(x, dfsz(x));
  S2[Centroid] = 1;

  for(int v : adj[Centroid])
    if(not S2[v])
      p[cenotroid_descomposition(v)] = Centroid;
  
  return Centroid;
}

bool parent(int x, int y){
  return L[x] <= L[y] and R[y] <= R[y]; 
}

void update(int x, int v){
  int y = x;
  while(y){
    if(parent(x, y)) ans[y] += v;
    y = p[y];
  }
}

void query(int x){
  int y = x;
  int answer = 0;
  while(y){
    if(parent(y, x)) answer += ans[y];
    y = p[y];
  }
  return answer;
}