题解：P3603 雪辉

Ybll_ · 2025-05-30 15:05:08 · 题解

前置芝士：

1. 树链剖分
2. 分块
3. bitset

思路：

树分块板子，不会的话建议先去把【模板】树分块 AC 了。

先树剖，然后分块，记录每一个块和每一段连续块的 bitset，接下来的每一个询问，把每一个树链上的若干条重链的 bitset 并起来即可。

第一个问题，我们只需要输出 bitset 中 1 的个数，

第二个问题，我们需要输出 bitset 中的第一个 0，即把 bitset 按位取反后的第一个 1，可以用 _Find_first() 函数解决。

代码：

#include<bits/stdc++.h>
#define il inline
using namespace std;
il int read()
{
    int x=0,f=1;
    char c;
    while(!isdigit(c=getchar()))
    {
        if(c=='-')f=-1;
    }
    while(isdigit(c))
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
il void writing(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)writing(x/10);
    putchar(x%10+48);
}
il void write(int x,int y)
{
    writing(x);
    printf(" ");
    writing(y);
    puts("");
}
const int N=1e5+5,M=3e4+5;
struct node
{
    int id,top,sum,sz,son,fa,dep;
}a[N];
struct edge
{
    int to,next;
}G[N*2];
struct block
{
    int l,r;
}b[320];
int sum[N],n=read(),top,head[N],cnt,to[N],last;
bool fl;
bitset<M>f[320][320],ans;
il void add(int u,int v)
{
    G[++top]={v,head[u]};
    head[u]=top;
}
il void DFS1(int u,int fa)
{
    a[u].fa=fa;
    a[u].dep=a[fa].dep+1;
    a[u].sz=1;
    for(int i=head[u];i;i=G[i].next)
    {
        if(G[i].to==fa)continue;
        DFS1(G[i].to,u);
        a[u].sz+=a[G[i].to].sz;
        if(a[a[u].son].sz<a[G[i].to].sz)a[u].son=G[i].to;
    }
}
il void DFS2(int u,int topx)
{
    a[u].id=++cnt;
    a[u].top=topx;
    a[cnt].sum=sum[u];
    if(!a[u].son)return;
    DFS2(a[u].son,topx);
    for(int i=head[u];i;i=G[i].next)
    {
        if(G[i].to==a[u].fa||G[i].to==a[u].son)continue;
        DFS2(G[i].to,G[i].to);
    }
}
il void query_block(int l,int r)
{
    if(to[l]==to[r])
    {
        for(;l<=r;l++)
        {
            ans.set(a[l].sum);
        }
        return;
    }
    ans|=f[to[l]+1][to[r]-1];
    for(int i=l;i<=b[to[l]].r;i++)
    {
        ans.set(a[i].sum);
    }
    for(int i=b[to[r]].l;i<=r;i++)
    {
        ans.set(a[i].sum);
    }
}
il void query_range(int x,int y)
{
    if(fl)
    {
        x^=last;
        y^=last; 
    }
    while(a[x].top!=a[y].top)
    {
        if(a[a[x].top].dep<a[a[y].top].dep)swap(x,y);
        query_block(a[a[x].top].id,a[x].id);
        x=a[a[x].top].fa;
    }
    if(a[x].dep>a[y].dep)swap(x,y);
    query_block(a[x].id,a[y].id);
}
signed main()
{
    int Q=read(),lst=0,len;
    fl=read();
    len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        sum[i]=read();
    }
    for(int i=1,u,v;i<n;i++)
    {
        add(u=read(),v=read());
        add(v,u);
    }
    DFS1(1,0);
    DFS2(1,1);
    for(int i=1;i<=n;i++)
    {
        to[i]=(i-1)/len+1;
        f[to[i]][to[i]].set(a[i].sum);
    }
    for(int i=1;i<=to[n];i++)
    {
        b[i].l=b[i-1].r+1;
        b[i].r=i*len;
    }
    b[to[n]].r=n;
    for(int i=1;i<to[n];i++)
    {
        for(int j=i+1;j<=to[n];j++)
        {
            f[i][j]=f[i][j-1]|f[j][j];
        }
    }
    while(Q--)
    {
        int q=read();
        ans.reset();
        while(q--)
        {
            int x=read(),y=read();
            query_range(x,y);
        }
        int ans1=ans.count(),ans2=(~ans)._Find_first();
        last=ans1+ans2;
        write(ans1,ans2);
    }
    return 0;
}