【前后缀技巧】2022牛客多校3 A

骑猪看日落 2024-02-26 02:53 6阅读 0赞

[登录—专业IT笔试面试备考平台\_牛客网][IT]

题意：

![74cf1b5348aa4c638b3419d0687f5169.png][]

思路：

这种是典中典中典，对于gcd，背包问题都是一样的处理方式

预处理出前缀lca和后缀lca，枚举哪个消失即可，可以统计方案数

Code：

#include <bits/stdc++.h>
    
    constexpr int N = 2e5 + 10;
    constexpr int mod = 1e9 + 7;
    constexpr int Inf = 0x3f3f3f3f;
    constexpr double eps = 1e-10;
    
    std::vector<int> adja[N], adjb[N];
    
    int n, k;
    int x[N];
    int a[N], b[N];
    int pa[N], pb[N];
    int depa[N], depb[N];
    int Fa[N][33], Fb[N][33];
    int prea[N], sufa[N], preb[N], sufb[N];
    
    void dfs1(int u, int fa) {
        depa[u] = depa[fa] + 1;
        Fa[u][0] = fa;
        for (int j = 1; j <= 30; j ++) Fa[u][j] = Fa[Fa[u][j - 1]][j - 1];
        for (auto v : adja[u]) {
            if (v == fa) continue;
            dfs1(v, u);
        }
    }
    void dfs2(int u, int fa) {
        depb[u] = depb[fa] + 1;
        Fb[u][0] = fa;
        for (int j = 1; j <= 30; j ++) Fb[u][j] = Fb[Fb[u][j - 1]][j - 1];
        for (auto v : adjb[u]) {
            if (v == fa) continue;
            dfs2(v, u);
        }
    }
    int lca_a(int u, int v) {
        if (depa[u] < depa[v]) std::swap(u, v);
        for (int j = 30; j >= 0; j --) {
            if (depa[Fa[u][j]] >= depa[v]) {
                u = Fa[u][j];
            }
        }
        if (u == v) return u;
        for (int j = 30; j >= 0; j --) {
            if (Fa[u][j] != Fa[v][j]) {
                u = Fa[u][j];
                v = Fa[v][j];
            }
        }
        return Fa[u][0];
    }
    int lca_b(int u, int v) {
        if (depb[u] < depb[v]) std::swap(u, v);
        for (int j = 30; j >= 0; j --) {
            if (depb[Fb[u][j]] >= depb[v]) {
                u = Fb[u][j];
            }
        }
        if (u == v) return u;
        for (int j = 30; j >= 0; j --) {
            if (Fb[u][j] != Fb[v][j]) {
                u = Fb[u][j];
                v = Fb[v][j];
            }
        }
        return Fb[u][0];
    }
    void solve() {
        std::cin >> n >> k;
        for (int i = 1; i <= k; i ++) std::cin >> x[i];
    
        for (int i = 1; i <= n; i ++) {
            std::cin >> a[i];
        }
        for (int i = 2; i <= n; i ++) {
            std::cin >> pa[i];
            adja[pa[i]].push_back(i);
            adja[i].push_back(pa[i]);
        }
        for (int i = 1; i <= n; i ++) {
            std::cin >> b[i];
        }
        for (int i = 2; i <= n; i ++) {
            std::cin >> pb[i];
            adjb[pb[i]].push_back(i);
            adjb[i].push_back(pb[i]);
        }
    
        dfs1(1, 0);
        dfs2(1, 0);
    
        prea[1] = x[1];
        for (int i = 2; i <= k; i ++) {
            prea[i] = lca_a(prea[i - 1], x[i]);
        }
        preb[1] = x[1];
        for (int i = 2; i <= k; i ++) {
            preb[i] = lca_b(preb[i - 1], x[i]);
        }
        sufa[k] = x[k];
        for (int i = k - 1; i >= 1; i --) {
            sufa[i] = lca_a(sufa[i + 1], x[i]);
        }
        sufb[k] = x[k];
        for (int i = k - 1; i >= 1; i --) {
            sufb[i] = lca_b(sufb[i + 1], x[i]);
        }
    
        int ans = 0;
        int cur1 = sufa[2];
        int cur2 = sufb[2];
        if (a[cur1] > b[cur2]) ans ++;
    
        for (int i = 2; i <= k - 1; i ++) {
            int cur1 = lca_a(prea[i - 1], sufa[i + 1]);
            int cur2 = lca_b(preb[i - 1], sufb[i + 1]);
            if (a[cur1] > b[cur2]) ans ++;
        };
    
        cur1 = prea[k - 1];
        cur2 = preb[k - 1];
        if (a[cur1] > b[cur2]) ans ++;
    
        std::cout << ans << "\n";
    }
    signed main() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    
        int t = 1;
        while(t --) {
            solve();
        }
        return 0;
    }

[IT]: https://ac.nowcoder.com/acm/contest/33188/A
[74cf1b5348aa4c638b3419d0687f5169.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/26/fa70d4c6047f43aeac4865d5c1a79bf2.png