Problem A: 种树
Description
很久很久以前，一个蒟蒻种了一棵会提问的树，树有\(n\)个节点，每个节点有一个权值，现在树给出\(m\)组询问，每次询问两个值：树上一组点对\((x,y)\)简单路径上不同权值的数量以及权值的\(\max\)为多少
然而某一天毒瘤胖子过来给树浇了点水，询问变成了每次求，一组点对\((x,y)\)简单路径上的不同权值的数量以及权值的\(mex\)
然而又过了两天毒瘤袁稳稳也过来给树浇了点水，询问变成了每次求若干组点对\((x,y)\)简单路径的并集上的不同权值的数量以及权值的\(mex\)（如有疑惑见\(HINT\)）
然后蒟蒻就菜哭在树下了qwq并且毫不负责任地把这个问题丢给了刚好路过的你
因为这棵树受到了两个毒瘤的祝福，每次询问受到了加密，记\(lastans\)表示上一次询问的两个答案的和，这次询问中的读入的表示点对的两个数都要\(xor \ (lastans∗op)\)，其中\(op\in \{0,1\}\)，具体见数据范围
后话：然而毕竟是蒟蒻种的树，毒瘤的祝福并没有使这题送温暖的本质发生变化qwq
Input
第一行三个整数\(n,m,op\)
接下来一行\(n\)个整数表示每个节点的权值\(val_i\)
再接下来\(n−1\)行每行两个整数\(x,y\)表示树上的一条边
再接下来\(m\)组询问，每组询问第一行一个整数\(num\)表示点对的数量，接下来\(num\)行每行两个整数\((x,y)\)表示一组点对
Output
对于每组询问，输出一行两个整数分别表示不同权值的数量以及权值的\(mex\)
Sample Input
5 5 0
2 0 0 1 3
1 2
2 3
2 4
4 5
1 4 5
3 1 5 5 2 4 4
2 2 4 2 4
4 2 5 3 1 4 3 2 5
1 2 5
Sample Output
2 0
4 4
2 2
4 4
3 2
HINT
一些你可能根本不需要用到的说明：一个数集\(S\)的\(mex\)为最小的满足\(x\notin S\)的非负整数\(x\)
\(subtask1(20\%)\)：\(n,m≤1000,\sum num≤1000,op=0\)
\(subtask2(30\%)\)：\(n,m≤10^5,\sum num≤10^5\)，树是一条链，\(op=0\)
\(subtask3(50\%)\)：\(n,m≤10^5,\sum num≤10^5,0≤val_i≤30000\)
完 全 没 有 感 受 到 温 暖，虽 然 确 实 是 最 简 单 的 一 道，剩 下 两 道 我 改 不 出 来
30000这个数我们很容易除上个64哎
然后随便用树剖倍增之类的维护一下，发现单次操作复杂度达到了惊人的\(\log n\frac{val}{64}\)，显然没救了。
这时候就是分块出场的时候辣
因为询问的是链的信息，所以我们考虑对树的深度进行分块，既对树提取一定的关键点，相邻的关键点深度差不超过\(\sqrt n\)就可以了，这样我们就有了\(\sqrt n\)个关键点。
然后我们拿关键点拼吗？复杂度达到了更惊人的\(\sqrt n \frac{val}{64}\)
所以考虑先预处理在同一条到跟路径上关键点的路径信息，这里采用手写\(bitset\)的方法就可以做到\(O(1)\)整数与上\(bitset\)了，然后每个关键点向上与顺便更新一下就行了。
查询的时候，不完整的暴力跳，完整的做一次bitset之间的与运算就行了。
复杂度：\(O(n\sqrt n+q(\sqrt n+\frac{val}{64}))\)
Code:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ull unsigned long long
const int N=1e5+10,B=470;
const ull full=~0ull,cut=(1ull<<16)-1;
int ct[cut+1],n,m,op;
int cal(ull x){return ct[x&cut]+ct[x>>16&cut]+ct[x>>32&cut]+ct[x>>48&cut];}
using std::max;
struct Bitset
{
ull dx[B];
int len;
void clear(){memset(dx,0,sizeof(dx)),len=0;}
Bitset(){clear();}
void friend operator |=(Bitset &A,int x){A.dx[x>>6]|=1ull<<(x&63);A.len=max(A.len,x>>6);}
void friend operator |=(Bitset &A,Bitset B)
{
A.len=A.len>B.len?A.len:B.len;
for(int i=0;i<=A.len;i++) A.dx[i]|=B.dx[i];
}
int count()
{
int ret=0;
for(int i=0;i<=len;i++)
ret+=cal(dx[i]);
return ret;
}
int mex()
{
for(int i=0;i<=len;i++)
{
if(dx[i]==full) continue;
for(int j=0;j<64;j++)
if(!(dx[i]>>j&1))
return (i<<6)+j;
}
return 233;
}
}path[320][320],ans;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int f[N][19],dep[N],mxdep[N],id[N],rt[N],val[N],pre[N],H;
void dfs(int now)
{
for(int i=1;f[now][i-1];i++) f[now][i]=f[f[now][i-1]][i-1];
dep[now]=dep[f[now][0]]+1;
mxdep[now]=1;
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=f[now][0])
{
f[v][0]=now;
dfs(v);
mxdep[now]=max(mxdep[now],mxdep[v]+1);
}
if(mxdep[now]==H||now==1)
{
rt[id[now]=++rt[0]]=now;
mxdep[now]=0;
}
}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) return LCA(y,x);
for(int i=18;~i;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for(int i=18;~i;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
void query(int x,int y)
{
while(!id[x]&&x!=y) ans|=val[x],x=f[x][0];
if(x==y) {ans|=val[x];return;}
int s=x;
while(dep[pre[x]]>dep[y]) x=pre[x];
ans|=path[id[s]][id[x]];
while(dep[f[x][0]]>=dep[y]) x=f[x][0],ans|=val[x];
}
void Query(int x,int y)
{
int lca=LCA(x,y);
query(x,lca);
query(y,lca);
}
int main()
{
scanf("%d%d%d",&n,&m,&op);
for(int i=1;i<=cut;i++) ct[i]=ct[i>>1]+(i&1);
H=sqrt(n)+1;
for(int i=1;i<=n;i++) scanf("%d",val+i);
for(int u,v,i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(1);
for(int i=1;i<=rt[0];i++)
{
Bitset tmp;
tmp|=val[rt[i]];
path[i][i]=tmp;
for(int now=f[rt[i]][0];now;now=f[now][0])
{
tmp|=val[now];
if(id[now])
{
path[i][id[now]]=tmp;
if(!pre[rt[i]]) pre[rt[i]]=now;
}
}
}
for(int lastans=0,num,x,y,i=1;i<=m;i++)
{
scanf("%d",&num);
ans.clear();
for(int j=1;j<=num;j++)
{
scanf("%d%d",&x,&y);
x^=lastans*op,y^=lastans*op;
Query(x,y);
}
int t1=ans.count(),t2=ans.mex();
lastans=t1+t2;
printf("%d %d\n",t1,t2);
}
return 0;
}
2019.1.6