"Wei Lai Cup" 2022 Niuke summer multi school training camp 3 record

A-Ancestor

The main idea of the topic ： Give two trees （ The number of knots is the same ）, Every node in the tree has a value , And a set of key nodes , It is required to remove one of the key nodes , Make the remaining key nodes in A Treelike LCA Value ratio of B Treelike LCA It's worth more , Find the number of solutions .
practice ： If you want to quickly find the remaining key nodes LCA, Key nodes can be preprocessed , Calculate the prefix LCA, Go to a point and follow the suffix LCA Calculate again LCA You can get the remaining points LCA. Therefore, this question can enumerate after removing each key point LCA value .
principle ：

 With prea[i] Indicates the front of the key node i There's a point in A Treelike LCA,lsta[i] Indicates the number of key nodes i And the following points are A Treelike LCA
 that prea[i + 1] = LCA(prea[i], key[i + 1]), Empathy lsta[i - 1] = LCA(lsta[i], key[i - 1])
 Remove a dot j after , The remaining points LCA' by ：
LCA' = LCA(prea[j - 1], lsta[j + 1])
 Special judgment is required when removing the first and last points 

Code ：（ seek LCA Used interval RMQ, Euler Sequence ）

#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];        // Record the position of the node in the Euler sequence for the first time 
    int seq[N * 2];    // Record Euler sequence 
    int dep[N * 2];    // Record the depth of the corresponding subscript in the Euler sequence 
    int st[N * 2][20]; // st surface , Record the subscript with the smallest depth 
    int val[N];
    int tot = 0;
    bool vis[N];

    vector<int> son[N]; // Record the subtree of each node 

    void dfs(int u, int d) //  Construct Euler sequence ,u Represents the current node ,d Expressing depth 
    {
    
        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; // Every time you backtrack, you should add the current point to the Euler sequence again 
            dep[tot] = d;
        }
    }
    void st_create() // establish st surface 
    {
    
        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]; // When returning, convert the subscript into seq The values in the array 
    }

    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;
}