ToB企服应用市场:ToB评测及商务社交产业平台

标题: 牛客多校Ancestor(lca，集合的lca) [打印本页]
作者: 铁佛    时间: 2024-6-11 12:40
标题: 牛客多校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.
输入描述:

  1. 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).
  3. 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).
  5. 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.
  7. 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​.
  9. 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.
  11. 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​.
复制代码
输出描述:

  1. One integer indicating the answer.
复制代码
示例1
输入

  1. 5 3
  2. 5 4 3
  3. 6 6 3 4 6
  4. 1 2 2 4
  5. 7 4 5 7 7
  6. 1 1 3 2
复制代码
输出

  1. 1
复制代码
说明

  1. In first case, the key numbers are 5,4,3. 
  2. Remove key number 5, the lowest common ancestors of the vertices in A with the remaining key numbers is 2, in B is 3.
  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.
  4. Remove key number 3, the lowest common ancestors of the vertices in A with the remaining key numbers is 4, in B is 1.
  5. Only remove key number 5 satisfies the requirement.
复制代码
示例2
输入

  1. 10 3
  2. 10 9 8
  3. 8 9 9 2 7 9 0 0 7 4
  4. 1 1 2 4 3 4 2 4 7
  5. 7 7 2 3 4 5 6 1 5 3
  6. 1 1 3 1 2 4 7 3 5
复制代码
输出

  1. 2
复制代码
备注:

  1. 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，然后调用即可
代码：

  1. int n,k;
  2. int vea[maxj],veb[maxj];
  3. int lg[maxj];
  4. int x[maxj];
  5. void dd(){
  6.     for(int i=1;i<=n;++i)
  7.         lg[i]=lg[i-1]+(1<<lg[i-1]==i);
  8. }
  9. struct node{
  10.    
  11. int pp[maxj],las[maxj];
  12. int dep[maxj],vis[maxj],fa[maxj][100];
  13. vector<int>g[maxj];
  14. void add(int u,int v){
  15.     g[u].emplace_back(v);
  16. }
  17. void dfs(int now ,int pre){
  18.     dep[now]=dep[pre]+1;
  19.     fa[now][0]=pre;
  20.     for(int i=1;(1<<i)<=dep[now];++i){
  21.         fa[now][i]=fa[fa[now][i-1]][i-1];
  22.     }
  23.     for(int i=0;i<g[now].size();++i){
  24.         if(pre==g[now][i])continue;
  25.         dfs(g[now][i],now);
  26.     }
  27. }
  29. int lca(int x,int y){
  30.     if(dep[x]<dep[y])swap(x,y);
  31.     while(dep[x]>dep[y])
  32.         x=fa[x][lg[dep[x]-dep[y]]-1];
  33.     if(x==y)return x;
  34.     for(int k=lg[dep[x]];k>=0;--k){
  35.         if(fa[x][k]!=fa[y][k]){
  36.             x=fa[x][k];
  37.             y=fa[y][k];
  38.         }
  39.     }
  40.     return fa[x][0];
  41. }
  42. void dolca(){
  43.     dfs(1,-1);
  44.     pp[1]=x[1];
  45.     for(int i=2;i<=k;++i){
  46.         pp[i]=lca(pp[i-1],x[i]);
  47.     }
  48.     las[k]=x[k];
  49.     for(int i=k-1;i>=1;--i){
  50.         las[i]=lca(las[i+1],x[i]);
  51.     }
  52. }
  53. int asklca(int w){
  54.     if(w==1)return las[2];
  55.     if(w==k)return pp[k-1];
  56.     return lca(pp[w-1],las[w+1]);
  57. }
  58. }treea,treeb;//分treea和treeb两个对象
  60. void solve(){
  61.     cin>>n>>k;//用struct封装一下，函数重用
  62.     for(int i=1;i<=k;++i)cin>>x[i];
  63.     for(int i=1;i<=n;++i)cin>>vea[i];
  64.     for(int i=2;i<=n;++i){
  65.         int pa;cin>>pa;
  66.         treea.add(pa,i);
  67.     }
  68.     for(int i=1;i<=n;++i)cin>>veb[i];
  69.     for(int i=2;i<=n;++i){
  70.         int pa;cin>>pa;
  71.         treeb.add(pa,i);
  72.     }
  73.     dd();
  74.     treea.dolca();
  75.     treeb.dolca();
  76.     int ans=0;
  77. //     for(int i=1;i<=k;++i)cout<<treea.las[i]<<' ';
  78.     for(int i=1;i<=k;++i){
  79.         int aa=treea.asklca(i);
  80.         int bb=treeb.asklca(i);
  81. //         cout<<aa<<' '<<bb<<'\n';
  82.         if(vea[aa]>veb[bb])ans++;
  83.     }cout<<ans<<'\n';
  84. }
复制代码


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4