P7735题解

0 前言

做的非常困难的一道题目，好不容易过了，于是想要纪念一下。

然后踩了不少的坑，反映了我不少的问题，也确实需要记录一下。

1 题意

原题面写的非常形式化了

P7735

2 思路

其实我很想侧重于我的思考过程说一说，因为蒟蒻的思路可能会更加提供一些启发。

首先看到这道题，要对边打标记，还要对边去除标记，肯定是很不好做的。

我第一次就是卡在这个地方，不知道该从哪里入手。

但是当时还是在mx上课，于是ylq上课给我们放出这题的时候说了一句话提醒了我，大意就是把边的信息转化到点上，用每两个点颜色相同或者不同来判断两点之间是实边还是虚边（为防止歧义，下文使用”实边“代指原题目”重边“，”虚边“代指原题目”轻边“）。

那么有了这个提示思路就很明了了，给每个点染色，两点颜色相同边就是实边，不同则为虚边。然后拿一个线段树维护一下区间赋值和区间相同的相邻数对的数量就几乎是做完了。

3 实现

细节

到这里我觉得这题后面的部分就是一个板题。

然后写好了，过了样例，一交，5pts。

好吧其实是多测没清空线段树的lazytag，太唐了

又交了一下，45pts。

这时才是卡的开始。

我的思路是大体按照往常的树剖。同时由于需要关注区间的合并顺序和方向，在重链上合并答案的时候，由于都是自下往上跳的，因此可以在 $u$ 的一边和 $v$ 的一边都维护一个 $lst$，来表示上一条重链的末尾元素的颜色。如果当前点和 $lst$ 相同，那么就把答案加一。

这样乍一看是对的。但是不妨思考这样一个问题。我们的答案依赖 $lst$ 的判断来+1，那么假设 $u$ 直接更新到了 $LCA(u,v)$ 的地方，那么就会导致答案少 $1$。

我们当然可以在最后合并答案的时候特判，但是这样你要判断当前的 $lst$ 是从哪边更新上来，然后再取 $u,v$ 最后在同一条重链上的 $pre$ 或者 $suf$ 来更新。但是显然，这样的代码和逻辑非常复杂，有没有什么更加简单的方法呢？

我们考虑不使用 $lst$ 而使用所谓 $nxt$ 来更新。也就是判断下一条重链的末尾和当前重链的顶端是否可以合并信息。这样就可以不重不漏的统计答案。同时只需要额外实现一个支持单点查询颜色的函数，非常简单。

代码

丑陋的代码。

注意多测清空，尤其是线段树清空。

int deep[N],son[N],siz[N],fa[N],top[N],id[N],cnt;
vector<int> g[N];
int n,m,rt=1,cnt1;
void dfs0(int now,int father){
    deep[now]=deep[father]+1;
    fa[now]=father;
    siz[now]=1;
    for(auto &i:g[now]){
        if(i==father)continue;
        dfs0(i,now);
        siz[now]+=siz[i];
        if(siz[i]>siz[son[now]])son[now]=i;
    }
}
void dfs1(int now,int tp){
    top[now]=tp,id[now]=++cnt;
    if(son[now]==0){
        return;
    }
    dfs1(son[now],tp);
    for(auto &i:g[now]){
        if(i==fa[now]||i==son[now])continue;
        dfs1(i,i);
    }
}
struct node{
    int pre,suf,num;    
}tree[N*4];
int tag[N*4];
void pushup(int u){
    tree[u].pre=tree[lb].pre;
    tree[u].suf=tree[rb].suf;
    tree[u].num=tree[lb].num+tree[rb].num+(tree[lb].suf==tree[rb].pre);
}
void build(int now,int l,int r){
    if(l==r){tree[now]={++cnt1,cnt1,0};return;}
    int mid=(l+r)>>1;
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    pushup(now);
}
void change(int x,int len,int val){
    tag[x]=val;
    tree[x]={val,val,len-1};
}
void pushdown(int u,int l,int r){
    if(tag[u]){
        int mid=(l+r)>>1;
        change(lb,mid-l+1,tag[u]);
        change(rb,r-mid,tag[u]);
        tag[u]=0;
    }
}

void update(int u,int left,int right,int l,int r,int val){
    if(l<=left&&right<=r){      
        change(u,right-left+1,val);
    }else if(!(r<left||right<l)){
        int mid=(left+right)>>1;
        pushdown(u,left,right);
        update(lb,left,mid,l,r,val);
        update(rb,mid+1,right,l,r,val);
        pushup(u);
    }
}
node query(int u,int left,int right,int l,int r){
    if(l<=left&&right<=r){
        return tree[u];
    }else if(!(r<left||l>right)){
        int mid=(left+right)>>1;
        pushdown(u,left,right);
        if(r<=mid){return query(lb,left,mid,l,r);}
        elif(l>mid){return query(rb,mid+1,right,l,r);}
        else{
            auto lx=query(lb,left,mid,l,r),rx=query(rb,mid+1,right,l,r);
            node ret;
            ret.pre=lx.pre;
            ret.suf=rx.suf;
            ret.num=lx.num+rx.num+(lx.suf==rx.pre);
            return ret;
        }
    }else return (node){-1,-1,0}; 
} 
int query_point(int u,int l,int r,int pos){
    if(l==r)return tree[u].pre;
    int mid=l+r>>1;
    pushdown(u,l,r);
    if(pos<=mid)return query_point(lb,l,mid,pos);
    else return query_point(rb,mid+1,r,pos);
}
int querypath(int u,int v){
    int ret=0;
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]]){swap(u,v);}
        auto tmp=query(1,1,n,id[top[u]],id[u]);
        ret+=(tmp.num+(query_point(1,1,n,id[top[u]])==query_point(1,1,n,id[fa[top[u]]])));
        u=fa[top[u]]; 
    }
    if(deep[u]<deep[v]){swap(u,v);}
    auto tmp=query(1,1,n,id[v],id[u]);
    ret=ret+tmp.num;
    return ret;
}
void updatepath(int u,int v,int k){    
    while(top[u]!=top[v]){
        if(deep[top[u]]<deep[top[v]])swap(u,v);
        update(1,1,n,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(deep[u]<deep[v])swap(u,v);
    update(1,1,n,id[v],id[u],k);
}

signed main(){
    int t=read();
    while(t--){
        n=read();int q=read();
        cnt=0;
        cnt1=0; 
        for(int i=0;i<N;++i)tag[i]=0;
        for(int i=1;i<=n;++i){
            g[i].clear();
            son[i]=0;siz[i]=0;
        }
        for(int i=1;i<n;++i){
            int u=read(),v=read();
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs0(rt,0);
        dfs1(rt,rt);
        build(1,1,n);
        while(q--){
            int opt=read(),u=read(),v=read();
            if(opt==1){
                updatepath(u,v,++cnt1);
            }else{
                printf("%lld\n",querypath(u,v));
            }
        }
    }
}

4 时间复杂度分析

这东西还需要分析竟然。

线段树 $O(\log n)$，树剖 $O(\log n)$，预处理 $O(n)$ ，查询 $q$ 次，总的大概 $O(n\log^2n)$。

5 后记

新学年新气象。

大家开学快乐。

还是多听听歌吧还是。