牛客多校Ancestor(lca，集合的lca)

题目描述

NIO is playing a game about trees.

The game has two trees A,BA, BA,B each with NNN vertices. The vertices in each tree are numbered from 111 to NNN and the iii-th vertex has the weight viv_ivi​. The root of each tree is vertex 1. Given KKK key numbers x1,…,xkx_1,\dots,x_kx1​,…,xk​, find the number of solutions that remove exactly one number so that the weight of the lowest common ancestor of the vertices in A with the remaining key numbers is greater than the weight of the lowest common ancestor of the vertices in B with the remaining key numbers.

输入描述:

The first line has two positive integers N,K(2≤K≤N≤105)N,K (2 \leq K \leq N \leq 10^5)N,K(2≤K≤N≤105).

The second line has KKK unique positive integers x1,…,xK(xi≤N)x_1,\dots,x_K (x_i \leq N)x1​,…,xK​(xi​≤N).

The third line has NNN positive integers ai(ai≤109)a_i (a_i \leq 10^9)ai​(ai​≤109) represents the weight of vertices in A.

The fourth line has N−1N - 1N−1 positive integers {pai}\{pa_i\}{pai​}, indicating that the number of the father of vertices i+1i+1i+1 in tree A is paipa_ipai​.

The fifth line has nnn positive integers bi(bi≤109)b_i (b_i \leq 10^9)bi​(bi​≤109) represents the weight of vertices in B.

The sixth line has N−1N - 1N−1 positive integers {pbi}\{pb_i\}{pbi​}, indicating that the number of the father of vertices i+1i+1i+1 in tree B is pbipb_ipbi​.

输出描述:

One integer indicating the answer.

示例1

输入

5 3
5 4 3
6 6 3 4 6
1 2 2 4
7 4 5 7 7
1 1 3 2

输出

1

说明

In first case, the key numbers are 5,4,3. 
Remove key number 5, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 3.
Remove key number 4, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 1.
Remove key number 3, the lowest common ancestors of the vertices in A with the remaining key numbers is 4, in B is 1.
Only remove key number 5 satisfies the requirement.

示例2

输入

10 3
10 9 8
8 9 9 2 7 9 0 0 7 4
1 1 2 4 3 4 2 4 7
7 7 2 3 4 5 6 1 5 3
1 1 3 1 2 4 7 3 5

输出

2

备注:

The lowest common ancestor (LCA) (also called least common ancestor) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).(From Wiki.)

思路：

1，lca的板子题稍微进阶点，参看lca的文章

2，用两棵树存各自的前缀后缀lca，然后调用即可

代码：

int n,k;
int vea[maxj],veb[maxj];
int lg[maxj];
int x[maxj];
void dd(){
    for(int i=1;i<=n;++i)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}
struct node{
    
int pp[maxj],las[maxj];
int dep[maxj],vis[maxj],fa[maxj][100];
vectorg[maxj];
void add(int u,int v){
    g[u].emplace_back(v);
}
void dfs(int now ,int pre){
    dep[now]=dep[pre]+1;
    fa[now][0]=pre;
    for(int i=1;(1<<i)<=dep[now];++i){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=0;i<g[now].size();++i){
        if(pre==g[now][i])continue;
        dfs(g[now][i],now);
    }
}

int lca(int x,int y){
    if(dep[x]dep[y])
        x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y)return x;
    for(int k=lg[dep[x]];k>=0;--k){
        if(fa[x][k]!=fa[y][k]){
            x=fa[x][k];
            y=fa[y][k];
        }
    }
    return fa[x][0];
}
void dolca(){
    dfs(1,-1);
    pp[1]=x[1];
    for(int i=2;i=1;--i){
        las[i]=lca(las[i+1],x[i]);
    }
}
int asklca(int w){
    if(w==1)return las[2];
    if(w==k)return pp[k-1];
    return lca(pp[w-1],las[w+1]);
}
}treea,treeb;//分treea和treeb两个对象

void solve(){
    cin>>n>>k;//用struct封装一下，函数重用
    for(int i=1;i>x[i];
    for(int i=1;i>vea[i];
    for(int i=2;i>pa;
        treea.add(pa,i);
    }
    for(int i=1;i>veb[i];
    for(int i=2;i>pa;
        treeb.add(pa,i);
    }
    dd();
    treea.dolca();
    treeb.dolca();
    int ans=0;
//     for(int i=1;i<=k;++i)cout<<treea.las[i]<<' ';
    for(int i=1;i<=k;++i){
        int aa=treea.asklca(i);
        int bb=treeb.asklca(i);
//         cout<veb[bb])ans++;
    }cout<