Freaks City

This problem involves a tree with \(n\) nodes and \(n-1\) weighted edges. One edge can have its weight set to zero. Given \(T\) pairs of nodes \((u, v)\), the goal is to choose an edge to delete (set weight to zero) such that the maximum distance between any pair \((u, v)\) is minimized. Output this minimum possible maximum distance. Core Appro ...

Given an integer, determine if it is a palindrome. The straightforward apprroach is to treat the input as a string and check if it reads the same forwards and backwards, which can be done in O(n) time where n is the length of the string. A more efficient approach uses polynomial hashing with O(n) time complexity. We'll implement both forward an ...

Introduction During the summer vacation, I systematically studied various operations on trees through Teacher Tuo's sharing and discovered many useful techniques, which I now summarize. Teacher Tuo is amazing! One Problem Type: Batch processing queries of the form f(dep(lca(x,y))), where f(x) is a function of x. Approach: First perform tree ...

Introduction Given an integer array of size n. There are m queries, each query consists of two integers x and y, asking for the maximum value in the range [x, y] of the array. Approach A straightforward method would be to precompute f[i][j] representing the maximum value from index i to j. However, this approach is inefficient. Instead, we can ...

Tarjan's Algorithm for Strongly Connnected Components namespace TarjanSCC { int dfn[N], low[N], index, colorCount; int comp[N], size[N], value[N]; bool inStack[N]; stack<int> stk; vector<int> graph[N]; void tarjan(int u) { dfn[u] = low[u] = ++index; stk.push(u); inStack[u] = true; ...