thanks for Editorial :)))

Some of my thoughts: we can firstly compute the depth of each vertex and use a list to record the order of vertices in each depth. Let's consider the mentioned example (see the problem). the order of vertices in each depth is:
Depth 1: 1
Depth 2: 2, 3, 4
Depth 3: 5, 6
This process can help us quickly find the vertices in depth h for the required vertex v in the following. Going on, after that, we use DFS to record the in-time and out-time of each vertex. For the given example, we have the DFS order as follows:
DFS order: 1, 2, 2, 3, 5, 5, 6, 6, 3, 4, 4, 1
This can be addressed by applying the following pseudo-code:
time = 1;
DFS(vertex u)
    in[u] = time ++;
    for each son v
        DFS(v)
    out[u] = time++;
The above-mentioned two steps can be considered as a pre-processing operation. Then, for each query, denoted by <v, h>, we find the answer as follows.
Case 1: if h is no more than the depth of v, return "Yes".
Case 2: if v has no posterity that locates in depth h, then return "Yes".
Case 3: Otherwise, find the required vertices in depth h, and judge "Yes" or "No".
It can be said that, Case 1 is easy to solve. Here, Case 2 and Case 3 will utilize binary search (BS) to find the answer. Clearly, we will use BS to find the most left vertex (posterity) and the most right vertex (posterity) in the Depth-list of depth h for the vertex v. The BS exploits the in-time and out-time to find the most left vertex and the most right vertex. For example, if we want to find the most left vertex in depth h for the vertex v, we use the following pseudo-code:
l = 0, r = Depth[h].size() -1, ans_left = -1;
while( l <= r )
    m = (l + r) >> 1;
    if vertex Depth[h][m] is posterity of v
        ans_left = m, r = m -1;
    else if the ancestor of Depth[h][m] in depth "dep[v]" is in the left of v
        l = m + 1;
    else
        r = m -1;
Here, we will utilize the in-time and out-time of a vertex to judge that: whether a vertex A is the ancestor of a vertex B, or the left/right one of the ancestor of B in the Depth-list.
An accepted source code: 12519227

Let's assume f(x1, y1, x2, y2) be the function which gives the number of ways of going from point (x1, y1) to (x2, y2).

Now, the basic recurrence without memoization can be seen as :

f(x1, y1, x2, y2) :
  if S[x1][y1] != S[x2][y2] : return 0
  if x1 > x2 or y1 > y2 : return 0

  // include the base case when have two neighbouring cells or single cell
  // if neighbouring cells have same value return 1
  // else return 0

  ans = 0
  ans = ans + f(x1 + 1, y1, x2 - 1, y2)
  ans = ans + f(x1, y1 + 1, x2 - 1, y2)
  ans = ans + f(x1 + 1, y1, x2, y2 - 1)
  ans = ans + f(x1, y1 + 1, x2, y2 - 1)
  return ans

Also, one argument in the recursive function is dependent on other 3, if we know x1, y1 and x2, we could compute y2 because the points are such that the manhattan distance beetween (1, 1), (x1, y1) and (n, n) and (x2, y2) are same.

So, we could have three arguments to the recurrence. And as there's no loop inside, time complexity of the solution after memoization would be O(n^3). But, space complexity will also be O(n^3). To make the solution run in required space (256MB), observe the fact that the current layer (equidistant set of points from (0, 0)) is only dependent on next set of layers (points with distance one more) we could write a bottom up dp with O(n^2) space. Storing just last one calculated layer everytime.

I wrote top-down dp with memoization, got Memory Limit Exceeded, couldn't code bottom-up dp properly in time! :'(

I solved it with the same complexity but using binary indexed tree

But this overkilles the problem alot in my opinion

This solution is the sane as before but without logn

I also tried to solve C this way, but got wrong answer. Could you take a look at my code? 12511578

At first I was trying to come up with a solution similar to the editorial, but then I realised that a change in F is only influenced by the neighbours.

Anyways, here is my solution if anybody needs more help: 12512037

Great, thanks, so simple :) AC 12522984

Consider the simplest case: The string, of length L, is formed by all dots. Clearly f(s) = L - 1.

Imagine there k strings of consecutive dots of length L₁, L₂, ... L_k, separated by non-dot characters, the answer is just taking the sum of respective reductions, namely,

Let's see how we can perform updates in constant time.

Case 1: A segment's boundary becomes a non dot character. Number of dots reduced by 1, and number of segments is reduced by at most 1, depending on whether the segment is of length 1 or not. So the answer is reduced by at most 1.

Case 2: A segment's boundary is extended by 1, but not merging other segments. Number of dots is increased by 1, number of segments unchanged. So the answer is increased exactly by 1.

Case 3: A new segment is added (of length 1). This is the same as Case 2.

Case 4: One segment is broken by two non empty segments (otherwise, it's just case 1). In this case, number of dots is reduced by 1, the number of segment is increase by 1. So the answer is reduced by 2.

Case 5: Two non empty segments are merged. Number of dots is increased by 1, and the number of segments is reduced by 1. So the answer is increased by 2.

So you need to check neighbors of the changing position to see which case the operation falls into and update the answer in constant time accordingly.

Each substitution on s[xi] (ci' -> ci) will only effect s[xi]'s two neighbors(s[xi-1] and s[xi+1], if it has). Only need to recalculate the value on (s[xi-1], s[xi], s[xi+1]).

Your solution O(m * log * 26 + n). It is close to time limit.

My solution took 1996 ms. I'm running in the house yelling "Damn!".

If A is greater than the number of M, we are winning on any value from A to N.

Where is the input string?

Yes

F(...) = 2 (... -> .. -> .)

F(.a.) = 0 (.a.)

F(.ab) = 0 (.ab)

Instead of an array using a balanced search tree. The need for surgery to insert and retrieve an item.

ou[x][y] the position of the cell (x, y) on the diagonal.

in[x][y] the number and position of the diagonal of the coordinate cell.

hi if you see this comments please do tell me to if you found the ans

if you read the output section carefully you will notice that the problem say " If there are multiple such values, print the minimum of them."

so in your case you can choose any number because all numbers there probability is zero but the minimum one is "1".

How do you use DSU on trees in this problem?

Both have same probability and since m-1<m+1, we use m-1. The problem statement states that "If there are multiple such values, print the minimum of them."