Problem A: 种树解题报告

Problem A: 种树

Description

很久很久以前，一个蒟蒻种了一棵会提问的树，树有(n)个节点，每个节点有一个权值，现在树给出(m)组询问，每次询问两个值：树上一组点对((x,y))简单路径上不同权值的数量以及权值的(max)为多少

然而某一天毒瘤胖子过来给树浇了点水，询问变成了每次求，一组点对((x,y))简单路径上的不同权值的数量以及权值的(mex)

然而又过了两天毒瘤袁稳稳也过来给树浇了点水，询问变成了每次求若干组点对((x,y))简单路径的并集上的不同权值的数量以及权值的(mex)（如有疑惑见(HINT)）

然后蒟蒻就菜哭在树下了qwq并且毫不负责任地把这个问题丢给了刚好路过的你

因为这棵树受到了两个毒瘤的祝福，每次询问受到了加密，记(lastans)表示上一次询问的两个答案的和，这次询问中的读入的表示点对的两个数都要(xor (lastans∗op))，其中(opin {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

HINT

一些你可能根本不需要用到的说明：一个数集(S)的(mex)为最小的满足(x otin 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 nfrac{val}{64})，显然没救了。

这时候就是分块出场的时候辣

因为询问的是链的信息，所以我们考虑对树的深度进行分块，既对树提取一定的关键点，相邻的关键点深度差不超过(sqrt n)就可以了，这样我们就有了(sqrt n)个关键点。

然后我们拿关键点拼吗？复杂度达到了更惊人的(sqrt n frac{val}{64})

所以考虑先预处理在同一条到跟路径上关键点的路径信息，这里采用手写(bitset)的方法就可以做到(O(1))整数与上(bitset)了，然后每个关键点向上与顺便更新一下就行了。

查询的时候，不完整的暴力跳，完整的做一次bitset之间的与运算就行了。

复杂度：(O(nsqrt 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
",t1,t2);
    }
    return 0;
}

2019.1.6