“蔚来杯“2022牛客暑期多校训练营3 A.Ancestor LCA+暴力计数

A.Ancestor

题目分析

给出两棵编号$1-n$的树$A,B$，$A,B$树上每个节点均有一个权值，给出$k$个关键点的编号$x_1\dots x_n$，问有多少种方案使得去掉恰好一个关键点使得剩余关键点在树$A$上$LCA$的权值大于树$B$上$LCA$的权值。

处理出所有关键节点的前缀$LCA$和后缀$LCA$，然后枚举所有的关键节点求$LCA$后$Check$计数即可。

Code

#include <bits/stdc++.h>
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 862118861;

int a[N], b[N], key[N];
vector<int> g1[N], g2[N];

struct LCA{
    
    struct edge{
     int to, len, next; } E[N];
    int cnt, last[N], fa[N], top[N], deep[N], siz[N], son[N], val[N];
    void addedge(int a, int b, int len = 0){
    
        E[++cnt] = (edge){
    b, len, last[a]}, last[a] = cnt;
    }
    void dfs1(int x){
    
        deep[x] = deep[fa[x]] + 1;
        siz[x] = 1;
        for (int i = last[x]; i; i = E[i].next){
    
            int to = E[i].to;
            if (fa[x] != to && !fa[to]){
    
                val[to] = E[i].len;
                fa[to] = x;
                dfs1(to);
                siz[x] += siz[to];
                if (siz[son[x]] < siz[to]) son[x] = to;
            }
        }
    }
    void dfs2(int x){
    
        if (x == son[fa[x]]) top[x] = top[fa[x]];
        else top[x] = x;
        for (int i = last[x]; i; i = E[i].next)
            if (fa[E[i].to] == x && fa[E[i].to] != E[i].to) dfs2(E[i].to);
    }
    void init(int root) {
     dfs1(root), dfs2(root); }
    int query(int x, int y){
    
        for (; top[x] != top[y]; deep[top[x]] > deep[top[y]] ? x = fa[top[x]] : y = fa[top[y]]);
        return deep[x] < deep[y] ? x : y;
    }
}ta, tb;

int pa[N], pb[N], sa[N], sb[N];

inline void solve(){
    
    int n = 0, k = 0; cin >> n >> k;
    for(int i = 1; i <= k; i++) cin >> key[i];
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 2; i <= n; i++){
    
        int fa; cin >> fa;
        ta.addedge(fa, i), ta.addedge(i, fa);
    }
    for(int i = 1; i <= n; i++) cin >> b[i];
    for(int i = 2; i <= n; i++){
    
        int fa; cin >> fa;
        tb.addedge(fa, i), tb.addedge(i, fa);
    }
    ta.init(1), tb.init(1);
    pa[1] = pb[1] = key[1], sa[k] = sb[k] = key[k];
    for(int i = 2; i <= k; i++) 
        pa[i] = ta.query(pa[i - 1], key[i]), pb[i] = tb.query(pb[i - 1], key[i]);
    for(int i = k - 1; i >= 1; i--)
        sa[i] = ta.query(sa[i + 1], key[i]), sb[i] = tb.query(sb[i + 1], key[i]);
    int ans = 0;
    for(int i = 1; i <= k; i++){
    
        int qa = 0, qb = 0;
        if(i == 1){
    
            qa = sa[i + 1], qb = sb[i + 1];
        } else if(i == k){
    
            qa = pa[i - 1], qb = pb[i - 1];
        } else {
    
            qa = ta.query(pa[i - 1], sa[i + 1]);
            qb = tb.query(pb[i - 1], sb[i + 1]);
        }
        if(a[qa] > b[qb]) ans++;
    }
    cout << ans << endl;
}

signed main(){
    
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}