I don't have time to write in detail, until I click.

A-Kirill And The Game

Title Solution

Multiply every number from xxx to yyy by kkk. As long as there is a number greater than lll and less than rrr, it can be yes yes yes. If there is no one, it can be no no no

B-Gleb And Pizza

Title Solution

Geometry problems

C-Ilya And The Tree

Title Solution

Almost violent memory search

D-Vitya and Strange Lesson

Title Solution

01 trie template at a glance

E-Nikita and game

The main idea of the topic

In this paper, a graph is given. Each time a point is added after a point on the tree to form a new tree. How many points can be used as the end point of the tree diameter.

Title Solution

Starting from a certain point, the farthest point on this tree must be the end of its diameter. Starting from these points, the farthest point from them is also the end of its diameter, so it can be divided into three kinds of points: 1: the point farthest from the root; 2: the point farthest from the point of type 1; 3: the point with properties of type 1 and type 2 at the same time; the point difficult to deal with is type 3. Through observation, we can draw a conclusion If the diameter changes, the third point of the previous graph will not become the third point;
Then, the method is to create two sets, and store the first two points respectively. The third type of point exists in the first or second class. When the diameter changes, enumerate the set it is in. If the distance from a point to it is still the maximum distance, add it to another set.
Because only the third type of point will enter the set twice, the complexity is nlogn.

#include <bits/stdc++.h>
using namespace std;
namespace IOstream {
    #define gc getchar
    template <typename T> inline void read(T &x) {
        x = 0; T fl = 1; char c = 0;
        for (; c < '0' || c > '9'; c = gc()) if (c == '-') fl = -1;
        for (; c >= '0' && c <= '9'; c = gc()) x = (x << 1) + (x << 3) + (c ^ 48);
        x *= fl;  
    }
    template <typename T> inline T sqr(T x) { return x * x; }
    template <typename T> inline void write(T x) {
        if (x < 0) putchar('-'), x *= -1;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T> inline T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
    template <typename T> inline void writeln(T x) { write(x); puts(""); }
    template <typename T> inline void writesp(T x) { write(x); putchar(' '); }
    #undef gc
} using namespace IOstream;
const int LOG = 27;
const int N = 300000 + 5;
int fa[N][LOG + 5];
int p1[N], p2[N], dep[N];
int n, m, cnt1, cnt2, MX = 0;
int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOG; ~i; i --) 
        if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
    if (u == v) return u;
    for (int i = LOG; ~i; i --) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i]; 
            v = fa[v][i];
        }
    }
    return fa[u][0];
}
int dis(int u, int v) {
    int LCA = lca(u, v);
    return dep[u] + dep[v] - 2 * dep[LCA];
}
int main() {
    read(n); 
    p1[++ cnt1] = 1;
    for (int i = 2, y; i <= n + 1; i ++) {
        read(y);
        fa[i][0] = y; dep[i] = dep[y] + 1; 
        for (int j = 1; j <= LOG; j ++) 
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
        int d1 = cnt1 == 0 ? 0 : dis(p1[1], i), d2 = cnt2 == 0 ? 0 : dis(p2[1], i);
        if (d1 > MX) {
            for (int j = 1; j <= cnt2; j ++) 
                if (dis(p2[j], i) == d1) p1[++ cnt1] = p2[j];
            cnt2 = 1;
            p2[1] = i; 
        } else if (d2 > MX) {
            for (int j = 1; j <= cnt1; j ++) 
                if (dis(p1[j], i) == d2) p2[++ cnt2] = p1[j];
            cnt1 = 1;
            p1[1] = i;
        } else if (d1 == MX) p2[++ cnt2] = i;
        else if (d2 == MX) p1[++ cnt1] = i;
        MX = max(MX, max(d1, d2));
        writeln(cnt1 + cnt2);
     }
    return 0;
}