“蔚来杯“2022牛客暑期多校训练营3记录

A-Ancestor

题目大意： 给两棵树（结点数相同），树上每个结点都有一个值，以及一个关键结点集合，要求去点关键结点中的一个，使得剩下的关键结点在A树的的LCA的值比B树的LCA的值要大，求方案数。
做法： 如果要快速地求出剩余关键结点的LCA，可以对关键结点进行预处理，计算其前后缀的LCA，去点一个点后根据前后缀的LCA再计算一次LCA即可得到剩余点的LCA。因此这题可以枚举去掉每个关键点后的LCA值。
原理：

以prea[i]表示关键结点的前i个点在A树的LCA，lsta[i]表示关键结点的第i个以及之后的点在A树的LCA
那么prea[i + 1] = LCA(prea[i], key[i + 1])，同理lsta[i - 1] = LCA(lsta[i], key[i - 1])
去掉一个点j后，剩余的点的LCA'为：
LCA' = LCA(prea[j - 1], lsta[j + 1])
当去掉第一个和最后一个点的时候需要特判

代码：（求LCA用的区间RMQ，欧拉序列）

#include <bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))
const int N = 2e5 + 5;
using namespace std;

struct lcatree
{
    
    int pos[N];        //记录结点在欧拉序列中第一次出现的位置
    int seq[N * 2];    //记录欧拉序列
    int dep[N * 2];    //记录欧拉序列中对应下标的深度
    int st[N * 2][20]; // st表，记录深度最小的下标
    int val[N];
    int tot = 0;
    bool vis[N];

    vector<int> son[N]; //记录每个结点的子树

    void dfs(int u, int d) // 构建欧拉序列，u表示当前结点，d表示深度
    {
    
        vis[u] = 1;
        pos[u] = ++tot;
        seq[tot] = u;
        dep[tot] = d;
        for (auto s : son[u])
        {
    
            if (vis[s]) continue;
            dfs(s, d + 1);
            seq[++tot] = u; //每次回溯要将当前点再次加入欧拉序列
            dep[tot] = d;
        }
    }
    void st_create() //创建st表
    {
    
        for (int i = 1; i <= tot; i++)
            st[i][0] = i;
        int k = log2(tot), f1, f2;
        for (int j = 1; j <= k; j++)
        {
    
            for (int i = 1; i <= tot - (1 << j) + 1; i++)
            {
    
                f1 = st[i][j - 1], f2 = st[i + (1 << (j - 1))][j - 1];
                st[i][j] = dep[f1] < dep[f2] ? f1 : f2;
            }
        }
    }
    int get_lca(int u, int v)
    {
    
        int l = pos[u], r = pos[v];
        if (l > r) swap(l, r);
        int k = log2(r - l + 1);
        int f1 = st[l][k], f2 = st[r - (1 << k) + 1][k];
        return dep[f1] < dep[f2] ? seq[f1] : seq[f2]; //返回时要将下标转化成seq数组中的值
    }

    void init(int n)
    {
    
        mem(vis, 0);
        int fa;
        for (int i = 1; i <= n; i++)
            cin >> val[i];
        for (int i = 2; i <= n; i++)
        {
    
            cin >> fa;
            son[fa].push_back(i);
        }
        dfs(1, 0);
        st_create();
    }
} treea, treeb;

int key[N], prea[N], preb[N], lsta[N], lstb[N];

signed main()
{
    
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, k, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= k; i++)
        cin >> key[i];
    treea.init(n);
    treeb.init(n);
    prea[1] = key[1];
    preb[1] = key[1];
    for (int i = 2; i <= k; i++)
    {
    
        prea[i] = treea.get_lca(prea[i - 1], key[i]);
        preb[i] = treeb.get_lca(preb[i - 1], key[i]);
    }
    lsta[k] = key[k];
    lstb[k] = key[k];
    for (int i = k - 1; i >= 1; i--)
    {
    
        lsta[i] = treea.get_lca(lsta[i + 1], key[i]);
        lstb[i] = treeb.get_lca(lstb[i + 1], key[i]);
    }
    for (int i = 1; i <= k; i++)
    {
    
        if (i == 1)
        {
    
            if (treea.val[lsta[2]] > treeb.val[lstb[2]])
                ans++;
        }
        else if (i == k)
        {
    
            if (treea.val[prea[k - 1]] > treeb.val[preb[k - 1]])
                ans++;
        }
        else
        {
    
            int lcaa = treea.get_lca(prea[i - 1], lsta[i + 1]);
            int lcab = treeb.get_lca(preb[i - 1], lstb[i + 1]);
            if (treea.val[lcaa] > treeb.val[lcab])
                ans++;
        }
    }
    cout << ans;
    return 0;
}