题解 SP10707 【COT2 - Count on a tree II】

VTloBong · 2020-04-07 07:59:52 · 题解

我有一莫队，可以过十万。

思路

看到这种询问与区间内某个数出现的次数有关的题，很容易想起莫队。但此题的询问是在树上，所以我们需要把树转化为线性结构。
通常把树转化为线性结构要利用dfs序,但dfs序并不适用于莫队。
好在天无绝人之路，dfs序不可用，但我们还有欧拉序。

1.欧拉序

dfs序为什么不适用于莫队？
在思考这个问题之前，我们不妨先想一下dfs序是什么。
dfs序,顾名思义，指每个节点在dfs深度优先遍历中的进栈的时间戳序列。一条树上简单路径在dfs序上被分为几段不相交的区间，因此，dfs序适用于维护的信息可以由区间合并而来的情况。
而欧拉序，即每个节点在dfs深度优先遍历中的进出栈的时间戳序列。如果把有进有出的点忽略，一条树上简单路径在欧拉序上就成为了一段连续的区间。因此，欧拉序适用于维护的信息可以由区间加减相邻元素而调整的情况。
口胡的结论：dfs序适用于维护的信息可以由区间合并而来的情，而欧拉序适用于维护的信息可以由区间加减相邻元素而调整的情况。（欢迎打脸）

2.假树上莫队

我们在点进栈时记一个时间戳st，出栈时再记一个时间戳ed。
每次询问的节点u,v（不妨设 st_u<st_v ）有两种情况：

u是v的祖先，路径在欧拉序上对应的区间为 [st_u,st_v] ;
u不是v的祖先，路径在欧拉序上对应的区间为 [ed_u,st_v] ，再加上lca的贡献。

我们可以树链剖分求lca,顺便在预处理时求出欧拉序。
开一个数组记录节点i在不在目前区间中，区间调整时，1表示需要删除，0表示需要加入。

代码

前方大常数警告


#include<cstdio>
#include<algorithm>
using namespace std;
//#define int long long
const int maxn=400005,sqrn=1005;
//离散化：
struct number{
    int data,id;
}lsh[maxn];
bool cmp1(number x,number y){
    return x.data <y.data ;
} 
//树剖：
struct edge{
    int to,next;
}e[maxn<<1];
int head[maxn],dfn[maxn<<1],st[maxn],ed[maxn],fa[maxn],dep[maxn],s[maxn],son[maxn],top[maxn];
inline void add_edge(int u,int v,int id){
    e[id].to=v,e[id].next=head[u],head[u]=id;
}
inline void build(int m){
    int u,v;m<<=1;
    for(register int i=1;i<=m;i+=2)
        scanf("%d%d",&u,&v),add_edge(u,v,i),add_edge(v,u,i+1);
}
inline void dfs1(int x){
    st[x]=++dfn[0],dfn[dfn[0]]=x,dep[x]=dep[fa[x]]+1,s[x]=1,son[x]=0;
    for(register int l=head[x],v;l;l=e[l].next){
        v=e[l].to;
        if(v==fa[x])continue;
        fa[v]=x,dfs1(v),s[x]+=s[v];
        if(s[v]>s[son[x]])son[x]=v;
    }
    ed[x]=++dfn[0],dfn[dfn[0]]=x;
}
inline void dfs2(int x){
    if(son[x])top[son[x]]=top[x],dfs2(son[x]);
    for(register int l=head[x],v;l;l=e[l].next){
        v=e[l].to;
        if(v==fa[x]||v==son[x])continue;
        top[v]=v,dfs2(v);
    }
}
inline int _lca(int u,int v){
    int t;
    while(top[u]^top[v]){
        if(dep[top[u]]<dep[top[v]])t=u,u=v,v=t;
        u=fa[top[u]];
    }return dep[u]>dep[v]?v:u;
}
//莫队： 
struct query{
    int l,r,lca,id;
}q[maxn];
int a[maxn],cnt[maxn<<1],ans,ls=1,rs,size,book[maxn],f[200000],n,m;
bool cmp2(query x,query y){
    return (x.l-1)/size==(y.l-1)/size?(((x.l-1)/size)&1?x.r<y.r:x.r>y.r ):(x.l-1)/size<(y.l-1)/size; 
}
inline void add(int k){
    if(!cnt[a[k]])ans++;
    cnt[a[k]]++;
}
inline void del(int k){
    cnt[a[k]]--;
    if(!cnt[a[k]])ans--;
}
inline void change(int k){
    book[k]?del(k):add(k);
    book[k]^=1;
}
main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i)
        lsh[i].id=i,scanf("%d",&lsh[i].data);
    sort(lsh+1,lsh+n+1,cmp1);
    for(int i=1,num=0;i<=n;i++){
        if(lsh[i].data!=lsh[i-1].data||i==1)num++;
        a[lsh[i].id]=num;
    }for(size=1;size*size<n;size++);
    f[1]=0,dfn[0]=0,top[1]=1,build(n-1),dfs1(1),dfs2(1);
    for(register int i=1,u,v,t;i<=m;++i){
        q[i].id=i,scanf("%d%d",&u,&v),q[i].lca=_lca(u,v);
        if(st[u]>st[v])t=u,u=v,v=t;
        if(q[i].lca==u)q[i].l=st[u],q[i].lca=0;
        else q[i].l=ed[u];
        q[i].r=st[v];
    }sort(q+1,q+m+1,cmp2);
    for(register int i=1;i<=m;++i){
        int nl=q[i].l ,nr=q[i].r ;
        while(rs<nr)rs++,change(dfn[rs]);
        while(ls>nl)ls--,change(dfn[ls]);
        while(ls<nl)change(dfn[ls]),ls++;
        while(rs>nr)change(dfn[rs]),rs--;
        if(q[i].lca)change(q[i].lca);
        f[q[i].id]=ans;
        if(q[i].lca)change(q[i].lca);
    }for(register int i=1;i<=m;++i)printf("%d\n",f[i]);
    return 0;
}