题解：P17855 [LBA-OI R6 C] 哥德巴赫猜想

· · 题解

赛时想的是主席树的做法，被卡空间了，然后就撞不过去了。
这里用的是自认为比较简单的树剖和线段树做法，时空都是单 \log 的做法，膜拜线性做法。

以下称 n 为节点数。

从 60 分的双 \log 做法开始考虑。

线段树处理出每个区间的最大值，然后每次跳链，将每条链加入一个全局大根堆。删点时，就将原来的链一分二，重新加入全局堆。

每次会加入 \log(n) 条链，最多会加入 m\log (n) 条，全局堆空间的瓶颈。
单次操作一是 \log^2(n)，时间的瓶颈。

我们想如果每次只加入一条链，每次查询 \log(n)，就能过。

每次只加入一条链还是很好实现的，只要记录好端点即可，那么每次查询怎么实现成单 \log。

观察每次跳链，从左区间到右区间的过程，只有一次线段树查询不是查当前点到链头。这一次因为左区间可以是链上的不同点，所以这一次不可省。

那么直接跳到链头的呢，我们可以在 dfs 时直接处理出来，每个点到所在链头的路径上最大值节点编号。
这样查询时每次跳到链头就可以 O(1) 查，最后不是跳到链头就线段树 \log (n) 查。
操作二就直接断链，由于我们的链认父亲，下半区间不一定是哪一条链上的儿子，为了下半区间方便，考虑转移时，直接写成左开右闭的区间。这里不懂的看看代码。

由于我们每次都是跳链的操作，所以操作二转移时，不需要考虑任何 dfn 序，因为左区间从一开始一直保持是右区间的祖先，所以最后跳链一定会相遇。

::::info[代码]

#include<bits/stdc++.h>
using namespace std;
char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
    return x*f;
}
int fat[1000005],size[1000005],dfn[1000005],dfncnt=0,mapp[1000005];
int premax[1000005];
int maxn[4000005],maxid[4000005],son[1000005],w[1000005];
int head[1000005],ecnt=0;
struct
{
    int v,next;
}edge[1000005];
void dfs(int u)
{
    size[u]=1;
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].v;
        dfs(v);
        size[u]+=size[v];
        if(size[v]>size[son[u]]) son[u]=v;
    }
}
int top[1000005];
void dfs2(int u,int root)
{
    dfn[u]=++dfncnt;
    mapp[dfncnt]=u;
    if(top[fat[u]]==root)
    {
        if(w[premax[fat[u]]]<w[u]) premax[u]=u;
        else premax[u]=premax[fat[u]];
    }
    else premax[u]=u;
    top[u]=root;
    if(son[u]) dfs2(son[u],root);
    for(int i=head[u];i;i=edge[i].next) 
    {
        int v=edge[i].v;
        if(v!=son[u]) dfs2(v,v);
    }
}
struct aa
{
    int l,r,id;
};
struct cmp
{
    bool operator()(const aa& x,const aa& y)
    {
        return w[x.id]<w[y.id];
    }
};
priority_queue<aa,vector<aa>,cmp> q;
void build(int cnt,int l,int r)
{
    if(l==r){maxn[cnt]=w[mapp[l]];maxid[cnt]=l;return ;}
    int mid=(r+l)>>1;
    build(cnt<<1,l,mid);build(cnt<<1|1,mid+1,r);
    if(maxn[cnt<<1]>maxn[cnt<<1|1]){maxn[cnt]=maxn[cnt<<1];maxid[cnt]=maxid[cnt<<1];}
    else{maxn[cnt]=maxn[cnt<<1|1];maxid[cnt]=maxid[cnt<<1|1];}
}
pair<int,int> query(int cnt,int l,int r,int jobl,int jobr)
{
    if(jobl<=l&&jobr>=r) return {maxn[cnt],maxid[cnt]};
    int mid=(r+l)>>1;
    int ans=0,k=0;
    if(jobl<=mid)
    {
        auto p=query(cnt<<1,l,mid,jobl,jobr);
        ans=p.first;k=p.second;
    }
    if(jobr>mid)
    {
        auto p=query(cnt<<1|1,mid+1,r,jobl,jobr);
        if(p.first>ans)
        {
            ans=p.first;k=p.second;
        }
    }
    return {ans,k};
}
int n,m;
void path_query(int l,int r)
{
    int k=0;int z=r;
    while(top[l]!=top[r])
    {
        if(w[premax[r]]>w[k]) k=premax[r];
        r=fat[top[r]];
    }
    if(r!=l)
    {
        auto p=query(1,1,n,dfn[l]+1,dfn[r]);//左开区间 
        if(p.first>w[k]) k=mapp[p.second];
    }
    if(k!=0) q.push((aa){l,z,k});
}
void add(int u,int v)
{
    edge[++ecnt].v=v;
    edge[ecnt].next=head[u];
    head[u]=ecnt;
}
int main()
{
    n=rd();m=rd();
    for(int i=1;i<=n;i++)
    {
        fat[i]=rd();
        if(fat[i]!=0) add(fat[i],i);
    }
    for(int i=1;i<=n;i++) w[i]=rd();
    for(int i=1;i<=n;i++)
    {
        if(fat[i]==0)
        {
            dfs(i);
            premax[i]=i;dfs2(i,i);
        }
    }
    build(1,1,n);
    long long last=0;int tot=0;
    for(int i=1;i<=m;i++)
    {
        int opt;opt=rd();
        if(opt==1)
        {
            int x;x=rd();
            path_query(0,x);//左边开区间到0
        }
        else
        {
            tot++;
            if(q.empty()) continue;
            aa k=q.top();q.pop();
            last^=(1ll*w[k.id]*tot);
            if(k.l!=k.id) path_query(k.l,fat[k.id]);
            if(k.r!=k.id) path_query(k.id,k.r);//左边开区间，直接用k.id即可。 
        }
    }
    printf("%lld",last);
}

::::

警示后人，不要用 vector 存边，空间巨大，对于树形结构边不多，用链式前向星飞快。