A.Ancestor
题目分析
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;
}