题目：Tokitsukaze and Synthesis and Traits

出处：牛客寒假训练营

Tokitsukaze 最近在玩 《苏菲的炼金工房2》。

游戏内有 n 种特性，一些特性在调和炼金道具时能合成更高级的特性。有 m 个特性合成公式，每条公式都是 a+b 的形式，即特性 a 与特性 b 在调和成功后能合成出高级特性。这里保证 特性 a 和特性 b 是两种不同的特性，并且每条公式合成出的高级特性互不相同。一些常用的特性合成公式比如：

全能力超强化 + 全能力加成 = 全能之力

优秀成果 + 专家的完成度 = 超级品质

自信重击 + 必中重击 = 一击必杀

Tokitsukaze 将进行 qqq 次调和。每次调和，她会在 kkk 种备选特性中选出其中 222 种进行调和，保证在同一次调和中没有相同编号的特性。 Tokitsukaze 是高级炼金术士，所以调和必定成功。她想知道在这次调和中，她可能获得的高级特性有多少种。

数据允许的复杂度为n*sqrtn

考虑分块。

按照点的度数分块。

sz=sqrt(n)

小点最多连sqrt(n)条边

大点连成一个图，每个点度大于等于sqrt(n)，那么 大图上的点数是m/sqrt(n)~sqrt(n)

ps:感觉可以近似

大点最多连m/sqrt(n)条边

q次询问是个幌子，因为它的总询问是1e5级别的。

复杂度是 n*sqrt(n)

为了不必要的tle，选择scanf和快读会更加有优势

#include<bits/stdc++.h>
using namespace std;
#define fp(i, a, b) for (int i=a;i<=b;++i)
#define fd(i, a, b) for (int i=a;i>=b;--i)
#define pii pair<int,int>
const int N=2e5+10;
int d[N];
vector<int>big[N];
vector<int>small[N];
int n,m,q;
bool vis[N];
int sb[N];
int flag[N];
int main()
{scanf("%d%d%d",&n,&m,&q);int sz=sqrt(n+0.5);sz=min(sz,400);vector<pii>edge;fp(i,1,m){int x,y;scanf("%d%d",&x,&y);d[x]++;d[y]++;edge.push_back({x,y});}fp(i,1,n){if(d[i]>=sz)flag[i]=1;}for(auto hh:edge){int u=hh.first;int v=hh.second;if(flag[u]>flag[v])swap(u,v);if(flag[u]){big[u].push_back(v);}else{small[u].push_back(v);}}fp(i,1,q){int k;scanf("%d",&k);fp(j,1,k){scanf("%d",&sb[j]);vis[sb[j]]=1;}int sum=0;fp(j,1,k){if(flag[sb[j]]==1){for(auto tox:big[sb[j]]){sum+=vis[tox]&&vis[sb[j]];}}else{for(auto tox:small[sb[j]]){sum+=vis[tox]&&vis[sb[j]];}}}fp(j,1,k){vis[sb[j]]=0;}printf("%d\n",sum);}return 0;
}