1759：采访计划
时间限制: 2000 ms 内存限制: 131072 KB
【题目描述】
公元2044年，人类将进入宇宙纪元。L国有n个星球，分别编号为1到n，每一星球上有一个球长。
因为历史的长期积淀，第i个星球上还有一位编号为i的德高望重的长者，因为长者德高望重，所以第i个星球的球长一定被第i位长者管辖且长者管辖自己。
每一位长者手里有一份名单Bi，上面记录着一些长者的编号。
因为一些奥妙重重的原因，第i位长者的名单上只可能有1至i-1中的一些编号并且保证不会重复。
因为长者都德高望重，所以第i位长者管辖第j位长者的充要条件是：对于每一个k属于Bi,第k位长者管辖第j位长者。
此时，有一位记者想对一些球长进行采访，为了保证采访顺利，他决定先与一些长者搞好关系，以便采访被这些长者管辖的球长。
为了与更多的球长谈笑风生，这位记者会给你提出m个询问。
第i个询问中记者会给你fi个长者的编号，你需要回答有多少个星球的球长至少直接或间接被一位长者管辖。m≤2000000 。
【输入】
第一行一个数n，表示星球的个数。
接下来n行，每一行描述一个Bi：首先给出Bi的大小szi（可能为0），接下来szi个数，描述Bi中的每一个元素。保证Bi中的数没有重复。
接下来一行，给出一个数m，表示询问的个数。
接下来m行，每一行描述一个询问：格式同上文对于集合Bi的格式。
【输出】
共m行，第i行输出第i次询问的答案。
【输入样例】
7
0
1 1
1 1
1 2
2 2 3
0
2 2 6
3
2 2 3
2 3 5
2 4 5
【输出样例】
3
3
4
【提示】
【样例解释】
对于第一个询问，2、3号长者都管辖1号长者，所以总共有3个球长可以被采访，编号分别为1，2，3。
对于第二个询问，3、5号长者都管辖1号长者，所以总共有3个球长可以被采访，编号分别为1，3，5。
对于第三个询问，4号长者管辖第1、2号长者，所以总共有4个球长可以被采访，编号分别为1，2，4，5。
特别说明：第5号长者没有管辖长者2，因为3∈B5但2不属于B3。但长者4管辖长者2，因为长者管辖自己。
说明：
图中省略了球长，编号代表长者有向边u→v表示u在Bv中
【数据规模及约定】
对于30%的数据，n,m≤100。
对于100%的数据，n,m≤200000，∑|Bi|≤2000000，询问中的∑|szi|≤2000000 。
【题解】
这题关键在于如何建树，发现如果令一个点的所有祖先均被他管辖，则第i个节点应该接到它名单中节点的lca下，因为需要被这些点都管辖。
边建树边倍增，建树复杂度nlogn。
考虑如何回答询问。
发现每个询问就是求给出所有点到根的并的节点数。考虑将所有节点按dfn排序，则将每个节点与其相邻的节点的lca加起来即为答案。
代码如下：
#include<bits/stdc++.h>
using namespace std; const int N=2e5+5; int n,last[N],size,f[N][20],m,dfn[N],hu[N],dep[N],cnt; struct pigu { int dao,ne; }a[N<<1]; inline void lingjiebiao(int x,int y) { a[++size].dao=y; a[size].ne=last[x]; last[x]=size; } inline int read() { int x=0,f=1; char c=getchar(); while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();} while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return x*f; } inline void lian(int x,int y) { f[x][0]=y;dep[x]=dep[y]+1;lingjiebiao(y,x); for(int i=1;f[f[x][i-1]][i-1];i++) f[x][i]=f[f[x][i-1]][i-1]; } inline int get_lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } inline void dfs(int now) { dfn[now]=++cnt; for(int i=last[now];i;i=a[i].ne) dfs(a[i].dao); } inline bool cmp(int x,int y) { return dfn[x]<dfn[y]; } int main() { n=read(); for(int i=1,x;i<=n;i++) { x=read(); int lca=0; if(x) lca=read(); for(int j=1,y;j<=x-1;j++) { y=read(); lca=get_lca(lca,y); } lian(i,lca); } m=read(); dfs(0); for(int i=1,x;i<=m;i++) { x=read(); for(int j=1;j<=x;j++) hu[j]=read(); sort(hu+1,hu+x+1,cmp); int ans=dep[hu[1]]; for(int j=2;j<=x;j++) ans+=dep[hu[j]]-dep[get_lca(hu[j],hu[j-1])]; cout<<ans<<"\n"; } }
View Code
