Boxes
There are N
boxes, indexed by a number from 1 to N
. 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.
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
(1≤N≤200000
), the number of boxes.
The second line contains N
integers. The ith integer is either the index of the box which contains the ith box, or zero if the i
th box is not contained in any other box.
The third line contains an integer Q
(1≤Q≤100000), the number of queries. The following Q lines will have the following format: on each line, the first integer M (1≤M≤20) is the length of the list of boxes in this query, then M
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 | Sample Output 1 |
|---|---|
5 |
5 |
【分析】给出N个盒子，其中一些盒子可能会被放进另一些盒子里，Q个询问，每次询问给出M个盒子序号，求这M个盒子包含的盒子总数。
很容易想到这题就是建树，然后求子树的size。关键是如何合并这些点，即判断父子关系。有两种方法，一种是LCA，另一种是维护DFN序，然后区间合并。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2e5+;
const int M = 1e6+;
int n,m,k,tot=,tim=,ans;
int head[N],vis[N],in[N];
int bg[N],ed[N],sz[N];
vector<int>root;
struct man{
int to,next;
}edg[N*];
void add(int u,int v){
edg[tot].to=v;edg[tot].next=head[u];head[u]=tot++;
in[v]++;
}
void dfs(int u,int fa){
bg[u]=++tim;
sz[u]=;
for(int i=head[u];i!=-;i=edg[i].next){
int v=edg[i].to;
if(v!=fa){
dfs(v,u);
sz[u]+=sz[v];
}
}
ed[u]=tim;
}
int ispre(int u,int v){
if(u==v)return ;
else {
if(bg[u]<=bg[v]&&ed[u]>=ed[v])return ;
else if(bg[u]>=bg[v]&&ed[u]<=ed[v])return -;
}
return ;
}
int main() {
met(head,-);
int u,v;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&v);
if(v)add(v,i);
}
for(int i=;i<=n;i++)if(in[i]==)root.pb(i);
for(int i=;i<root.size();i++){
int rt=root[i];
dfs(rt,);
}
scanf("%d",&m);
vector<int>vec;
while(m--){
scanf("%d",&k);
vec.clear();ans=;
scanf("%d",&u);
vec.pb(u);
for(int i=;i<k;i++){
scanf("%d",&v);
bool f=false;
for(int j=;j<vec.size();j++){
u=vec[j];
if(ispre(u,v)==){
f=true;
break;
}
else if(ispre(u,v)==-){
vec.erase(vec.begin()+j);
j--;
}
}
if(!f)vec.pb(v);
}
for(int i=;i<vec.size();i++){
u=vec[i];
//printf("u : %d sz[u] : %d\n",u,sz[u]);
ans+=sz[u];
}
printf("%d\n",ans);
}
return ;
}