Kattis

Boxes

There are $N$

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.

includegraphics[width=0.5 extwidth ]{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 $N$

The second line contains $N$

The third line contains an integer $Q$

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

题意是给你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("
");*/
 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
",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("
");*/
109             for (int i=1;i<=cnt;++i)
110                 if (!iip[i]){
111                     //printf("cnt %d
",inp[i]);
112                     tot+=sum[inp[i]];
113                 }
114 
115             printf("%d
",tot);
116         }
117     }
118     return 0;
119 }