无论你再怎么觉得稳，比赛完了之后仍会挂分，而且你会发现稍稍改下就他妈可以加几十分。这就是生活。

kal0rona

A – 历史行程

官方正解写的是 SA，我不会，所以我就搜了半天 SAM 的题解，发现了一种很好的做法。

我们考虑建个 SAM，并且用 set 维护 Right 集合。然后在 Link 树上 DFS。因为我们的每次询问下表是连续的，所以对于树上点 \(u\) 的 set 中的某一个下标而言，他所能做的贡献就是将和子树内其前驱后继进行更新，也就是两个三元组\((u_x, sub_1, dep_u)\)、\((sub_2, u_x, dep_u)\)。因为，如果\(u\)在\(sub\)中选\(y\)时，如果选到了更远的\(z\)，那么显然答案不如\((y, z)\)的优，因为其深度更大时就已经完成了更新。set 可以用启发式合并，具体方式类似于「春节十二响」，通过交换编号实现。

然后再排序 + 离线 + 扫描线找最大点即可，还是很有意思的。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2e6 + 200, bitnum = 17;
typedef unsigned long long ull;

int n, q, head[MAX_N], current, sid[MAX_N], tp_tot, ans[MAX_N];
char str[MAX_N];
set<int> st[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

struct triple
{
    int x, y, d;
    bool operator<(const triple &rhs) const { return x < rhs.x; }
} tps[MAX_N << 1], queries[MAX_N];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void fileIO()
{
    freopen("history.in", "r", stdin);
    freopen("history.out", "w", stdout);
}

struct node
{
    int ch[2], link, dep;
} nodes[MAX_N];

int roots[MAX_N], atPos[MAX_N], ptot = 1, last_ptr = 1;
int fa[20][MAX_N], tree[MAX_N];

inline int lowbit(int x) { return x & (-x); }

void update(int x, int d)
{
    for (; x <= n; x += lowbit(x))
        tree[x] = max(tree[x], d);
}

int query(int x, int ret = 0)
{
    for (; x; x -= lowbit(x))
        ret = max(ret, tree[x]);
    return ret;
}

void insert(int c, int pos)
{
    int pre = last_ptr, p = last_ptr = ++ptot;
    nodes[p].dep = nodes[pre].dep + 1, st[p].insert(pos);
    while (pre && nodes[pre].ch[c] == 0)
        nodes[pre].ch[c] = p, pre = nodes[pre].link;
    if (pre == 0)
        nodes[p].link = 1;
    else
    {
        int q = nodes[pre].ch[c];
        if (nodes[q].dep == nodes[pre].dep + 1)
            nodes[p].link = q;
        else
        {
            int clone = ++ptot;
            nodes[clone] = nodes[q], nodes[clone].dep = nodes[pre].dep + 1;
            nodes[q].link = nodes[p].link = clone;
            while (pre && nodes[pre].ch[c] == q)
                nodes[pre].ch[c] = clone, pre = nodes[pre].link;
        }
    }
}

void dfs(int u)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        dfs(edges[i].to);
        if (st[sid[edges[i].to]].size() > st[sid[u]].size())
            swap(sid[edges[i].to], sid[u]);
        for (set<int>::iterator it = st[sid[edges[i].to]].begin(); it != st[sid[edges[i].to]].end(); it++)
        {
            set<int>::iterator tmp = st[sid[u]].upper_bound(*it);
            if (tmp != st[sid[u]].end())
                tps[++tp_tot] = triple{*it, *tmp, nodes[u].dep};
            if (tmp != st[sid[u]].begin())
                tps[++tp_tot] = triple{*(--tmp), *it, nodes[u].dep};
            st[sid[u]].insert(*it);
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    // fileIO();
    scanf("%d%d%s", &n, &q, str + 1);
    for (int i = 1; i <= n; i++)
        insert(str[i] - '0', i);
    sid[1] = 1;
    for (int i = 2; i <= ptot; i++)
        addpath(nodes[i].link, i), sid[i] = i;
    dfs(1);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &queries[i].x, &queries[i].y), queries[i].d = i;
    sort(tps + 1, tps + 1 + tp_tot), sort(queries + 1, queries + 1 + q);
    int tp_ptr = tp_tot;
    for (int q_ptr = q; q_ptr >= 1; q_ptr--)
    {
        while (tp_ptr >= 1 && tps[tp_ptr].x >= queries[q_ptr].x)
            update(tps[tp_ptr].y, tps[tp_ptr].d), tp_ptr--;
        ans[queries[q_ptr].d] = query(queries[q_ptr].y);
    }
    for (int i = 1; i <= q; i++)
        printf("%d\n", ans[i]);
    return 0;
}

B – 跳蚤王国

先找到中心作为根，然后把根的儿子放到 vector 中称为「候补割点」。我们按照子树大小从大到小对「候补割点」进行排序，把前 \(x\) 个称为「割点」，其中这些点的子树大小和恰好大于等于 \(\frac{n}{2}\)。

现在我们考虑做若干次 DFS 来获取答案。我们先枚举割点做子树根做 DFS，每个点的答案就为\(x\)或\(x-1\)。如何判断是否减一？我们只需要判断割点根的向上树边是否有必要即可。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int head[MAX_N], current, n, siz[MAX_N], root, answer[MAX_N], acc, limit_id;
vector<int> vec;

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void fileIO()
{
    freopen("flea.in", "r", stdin);
    freopen("flea.out", "w", stdout);
}

bool compare(int a, int b) { return siz[a] > siz[b]; }

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void dfs(int u, int fa)
{
    int max_son = 0;
    siz[u] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, u), siz[u] += siz[edges[i].to], max_son = max(max_son, siz[edges[i].to]);
    max_son = max(max_son, n - siz[u]);
    if (max_son <= (n >> 1))
        root = u;
}

void getAns(int u, int fa)
{
    answer[u] = limit_id - (siz[u] + acc >= (n >> 1)) + 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            getAns(edges[i].to, u);
}

int main()
{
    // fileIO();
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for (int i = 1, u, v; i <= n - 1; i++)
        scanf("%d%d", &u, &v), addpath(u, v), addpath(v, u);
    dfs(1, 0), dfs(root, 0);
    for (int i = head[root]; i != -1; i = edges[i].nxt)
        vec.push_back(edges[i].to);
    sort(vec.begin(), vec.end(), compare);
    limit_id = -1;
    for (int i = 0, siz_ = vec.size(); i < siz_; i++)
    {
        acc += siz[vec[i]];
        if (acc >= (n >> 1))
        {
            limit_id = i;
            break;
        }
    }
    for (int i = 0; i <= limit_id; i++)
        acc -= siz[vec[i]], getAns(vec[i], root), acc += siz[vec[i]];
    if (limit_id != -1)
        acc -= siz[vec[limit_id]];
    for (int i = limit_id + 1, siz_ = vec.size(); i < siz_; i++)
        getAns(vec[i], root);
    for (int i = 1; i <= n; i++)
        printf("%d\n", answer[i]);
    return 0;
}

C – 围墙

首先，我们把\(i \to p_i\)进行连边，会得到一个有很多环的图。分析题意，我们发现这道题要求我们把一些边删去，留下\(\frac{n}{2}\)个单边，且每条边不相交。那么，对于长度为\(2\)的环，我们把编号小的点作为左括号，编号大的点作为右括号；对于长度为偶数的环，我们发现也只有两种选择，直接搜索即可。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 110;
typedef long long ll;
typedef pair<int, ll> pil;

int n, pi[MAX_N], deg[MAX_N], seq[MAX_N];

void fileIO()
{
    freopen("wall.in", "r", stdin);
    freopen("wall.out", "w", stdout);
}

bool dfs(int pos, int acc)
{
    if (acc < 0)
        return false;
    if (pos == n + 1)
        return true;
    if (seq[pos] != 0)
        return dfs(pos + 1, acc + seq[pos]);
    int x = pos, len = 0, sign = 1;
    while (len == 0 || x != pos)
        seq[x] = sign, x = pi[x], len++, sign = -sign;
    if (dfs(pos + 1, acc + seq[pos]))
        return true;
    x = pos, len = 0, sign = -1;
    while (len == 0 || x != pos)
        seq[x] = sign, x = pi[x], len++, sign = -sign;
    if (dfs(pos + 1, acc + seq[pos]))
        return true;
    seq[pos] = 0;
    return false;
}

int main()
{
    // fileIO();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &pi[i]);
    for (int i = 1; i <= n; i++)
        if (pi[i] > i && i == pi[pi[i]])
            seq[i] = 1, seq[pi[i]] = -1;
    if (dfs(1, 0))
        for (int i = 1; i <= n; i++)
            if (seq[i] == 1)
                putchar('(');
            else
                putchar(')');
    return 0;
}