首页 > 代码库 > Kattis - boxes （LCA）

Kattis - boxes （LCA）

2024-09-12 00:43:03   218人阅读

Boxes

There are NN boxes, indexed by a number from 11 to NN. Each box may (or not may not) be put into other boxes. These boxes together form a tree structure (or a forest structure, to be precise).

You have to answer a series of queries of the following form: given a list of indices of the boxes, find the total number of boxes that the list of boxes actually contain.

Consider, for example, the following five boxes.

技术分享

Figure 1: Sample input

  • If the query is the list “1”, then the correct answer is “5”, because box 1 contains all boxes.

  • If the query is the list “4 5”, then the correct answer is “2”, for boxes 4 and 5 contain themselves and nothing else.

  • If the query is the list “3 4”, then the correct answer is “2”.

  • If the query is the list “2 3 4”, then the correct answer is “4”, since box 2 also contains box 5.

  • If the query is the list “2”, then the correct answer is “3”, because box 2 contains itself and two other boxes.

Input

The first line contains the integer NN (1≤N≤2000001≤N≤200000), the number of boxes.

The second line contains NN-integers. The iith integer is either the index of the box which contains the iith box, or zero if the iith box is not contained in any other box.

The third line contains an integer QQ (1≤Q≤1000001≤Q≤100000), the number of queries. The following QQ lines will have the following format: on each line, the first integer MM(1≤M≤201≤M≤20) is the length of the list of boxes in this query, then MM integers follow, representing the indices of the boxes.

Output

For each query, output a line which contains an integer representing the total number of boxes

Sample Input 1

5
0 1 1 2 2
5
1 1
2 4 5
2 3 4
3 2 3 4
1 2
Sample Output 1
5
2
2
4
3

题意是给你n个盒子，它们之间互相嵌套，给你m个询问，每次问你cnt个盒子中一共有几个盒子。

显然盒子的嵌套关系可以转换成树的父子关系。假设询问中有1 2 号盒子，而且1号盒子包含了2号盒子，这时2号盒子就被cover掉了，我们统计时只统计没有被cover的盒子就行了。

这就转换成了给你cnt个点，去掉其中含有所有父子关系中的儿子们，剩下的点输出他们的孩子一共有多少就可以了。

 

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 const int maxn =200010+50;
  5 vector <int> son[maxn];//存儿子
  6 int fa[maxn][50];//fa[i][j]表示 节点i向上走2^j个节点会到达哪个节点
  7 int p[maxn];//模拟的队列
  8 int sum[maxn];//每个节点的子树（包括自己）的节点数目
  9 int dep[maxn];//每个节点深度
 10 int inp[50];//询问的点们
 11 bool iip[50];//是否被覆盖
 12 int n,m;
 13 void bfs(int x)
 14 {
 15     dep[x]=1;
 16     int w,r;//w r 分别是队首队尾的下标
 17     w=1;
 18     p[1]=x;//模拟的队首是x
 19     sum[x]=1;
 20     r=1;//队尾下标是1
 21     while(w<=r)//队首下标小于等于队尾下标，即队列非空
 22     {
 23         int u=p[w];w++;//去队首，pop队首
 24         for(unsigned int i=0;i<son[u].size();i++)//遍历当前节点的每一个儿子
 25         {
 26             int v=son[u][i];
 27             if(dep[v])continue;//如果当前节点的深度不是0，就是被访问过，continue
 28             dep[v]=dep[u]+1;//当前节点深度等于父节点深度+1
 29             sum[v]=1;//当前节点的子树节点数为1
 30             p[++r]=v;//将当前节点push到队列中去
 31         }
 32     }
 33     /* 由于我们是按照数组保存的队列，我们从最大的下标(此时这些节点的深度也是最大的一批)
 34         开始向上回溯，让他们的父节点的sum加上他们的sum
 35     */
 36     while(r>0)
 37     {
 38         sum[fa[p[r]][0]]+=sum[p[r]];
 39         r--;
 40     }
 41 }
 42 int findd(int x,int y)
 43 {
 44     if (x!=y&&dep[x]==dep[y]) return false;
 45     if (x==y) return true;
 46     if (dep[x]<dep[y]){int temp=x;x=y;y=temp;}//保证dep[x]>=dep[y]
 47     while (dep[x]>dep[y]){//从x往上跳，跳的步数为1,2,4,8...
 48         int j=0;
 49         while (dep[fa[x][j]]>dep[y]) ++j;
 50         if (dep[fa[x][j]]==dep[y]){x=fa[x][j];break;}//如果跳到了同一深度，更新下x
 51         x=fa[x][--j];//让x跳到深度<=y而且深度最大的节点
 52     }
 53     if (x==y)
 54         return y;//如果此时x==y,则y是x的父亲,x,y的LCA显然是y
 55     while (x!=y){
 56         int j=0;
 57         while (fa[x][j]!=fa[y][j]) ++j;//x,y一起往上跳，直至两个跳到同一个点
 58         if (j==0)//此时x,y是亲兄弟
 59             break;
 60         --j;
 61         x=fa[x][j],y=fa[y][j];
 62     }
 63     return fa[x][0];
 64 }
 65 int main()
 66 {
 67     //freopen("de.txt","r",stdin);
 68     while (~scanf("%d",&n)){
 69         for (int i=1;i<=n;++i){
 70             scanf("%d",&fa[i][0]);
 71             son[fa[i][0]].push_back(i);
 72         }
 73         for (int j=1,k=2;k<=n;++j,k*=2){
 74             for (int i=1;i<=n;++i)
 75                 fa[i][j]=fa[fa[i][j-1]][j-1];
 76                 /* i向上走2^j个点等于 i向上走2^(j-1)个点后再向上走2^(j-1)个点 */
 77         }
 78         memset(sum,0,sizeof sum);
 79         memset(dep,0,sizeof dep);
 80         bfs(0);//广搜
 81         /*printf("sum ");
 82         for (int i=0;i<=n;++i)
 83             printf("%d ",sum[i]);
 84         printf("\n");*/
 85         scanf("%d",&m);
 86         while (m--){
 87             int tot=0;
 88             int cnt;
 89             memset(inp,0,sizeof inp);
 90             memset(iip,false,sizeof iip);
 91             scanf("%d",&cnt);
 92             for (int i=1;i<=cnt;++i)
 93                 scanf("%d",&inp[i]);
 94             for (int i=1;i<=cnt-1;++i){
 95                 if (iip[i]) continue;
 96                 for (int j=i+1;j<=cnt;++j){
 97                     if (iip[j]) continue;
 98                     if (inp[i]==inp[j]){iip[j]=true;continue;}
 99                     int lca=findd(inp[i],inp[j]);
100                     //printf("%d %d lca is %d\n",i,j,lca);
101                     if (lca==0) continue;
102                     if (lca==inp[i]){iip[j]=true;continue;}
103                     if (lca==inp[j]){iip[i]=true;continue;}
104                 }
105             }
106             /*for (int i=1;i<=cnt;++i)
107                 printf("!%d ",iip[i]);
108             printf("\n");*/
109             for (int i=1;i<=cnt;++i)
110                 if (!iip[i]){
111                     //printf("cnt %d\n",inp[i]);
112                     tot+=sum[inp[i]];
113                 }
114 
115             printf("%d\n",tot);
116         }
117     }
118     return 0;
119 }

 

 

 

Kattis - boxes （LCA）


联系
我们