题解：P14411 [JOISC 2015] 道路建设 / Road Development

· · 题解

前置知识

并查集、树链剖分、线段树（其实就是标签）

思路

首先读题，我们发现，如果 u 和 v 在某个时刻已经联通了，那么后续再怎么建道路，u 和 v 之间是不可能再建一条别的道路的，话句话说，这是一个没有环的图。因此我们就可以知道，在任意时刻，这个图都是一个森林。

然后我们先思考 -1 怎么判断，注意到，如果在某个时刻 i，A_i 与 B_i 还没有联通，那么这个时候我们执行了 2 操作以后，输出就是 -1

接下来我们考虑不是 -1 的情况，首先，这个时候的 i，A_i 与 B_i 一定是联通的，同时，这两个点之间肯定只有一条路径，因此题目中说的所有的最短的路径上的道路全部铺设完全就是没用的，因为两点间的路径最多只有一条。这个时候我们就能看出一点不寻常了，因为 A_i 与 B_i 间只有一条路径，所以我们怎么改变这个森林的连通性，只要保证改变完之后，这个图仍然是个森林，那么就不会影响答案的计算。

因此，我们很自然地想到，先把森林建出来，即先把 1 操作的道路建出来，注意这个时候不考虑铺设道路的具体情况。

然后，我们现在再想啊，因为 A_i 与 B_i 联通，所以这两个点一定在一棵树上，嘶...... 在一棵树上，把两点间的路径上的边全部铺设上道路，然后查询这两个点之间的路径上未铺设道路的边有几条，欸，这不就是树链剖分的板子题吗，我们让铺设了的道路的边的权值为 1，反之为 0，建设道路操作就是区间赋 1，然后铺设道路操作就是区间赋 0。2 操作就是查询 A_i 到 B_i 路径上的权值和。但是，树剖维护的是点的信息，那么我们怎么维护边的信息呢？

我们可以令某个点 u 的权值表示的是 u 到它的父亲的边的权值，这样我们就把边上的修改改成了点上的修改。注意，我们如果修改 x 到 y 的路径上的边，那么我们不需要修改 y 这个点，只需要修改到 y 下面这个点。查询同理。

那么此时我们就可以写出代码

#include<iostream>
#include<cstdio>
#define lson root<<1
#define rson root<<1|1
using namespace std;
inline int read(){
    char ch=getchar();int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
    return x*f;
}
inline void write(int x){
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int N=4e5+10;
int n,q,h[N],tot;
struct oprtAtion{
    int type,u,v;//分别表示操作类型、起点,终点 
    int val;//如果type=1,那么这个表示的是当前这个操作给 u~v 上的路径加 val 
    int ans;//type=2时,答案是几 
}opt[N];
struct egde{
    int to,nxt;
}e[N];
void Add(int u,int v){
    e[++tot]={v,h[u]};
    h[u]=tot;
}
int fa[N];
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
bool merge(int x,int y){
    int fx=Find(x),fy=Find(y);
    if(fx==fy)return false;//不能合并 
    Add(x,y);//可以合并,建图 
    Add(y,x);
    fa[fx]=fy;//并查集维护连通性 
    return true;//成功合并 
}
bool check(int x,int y){//判断两个点是否联通 
    return Find(x)==Find(y);
}
//-------------------以下是很板的树剖---------------------
int top[N],son[N],siz[N],id[N],f[N],dep[N];
int cur;
void dfs1(int u,int fa){
    siz[u]=1,f[u]=fa,dep[u]=dep[fa]+1;
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
void dfs2(int u,int t){
    id[u]=++cur;
    top[u]=t;
    if(son[u])dfs2(son[u],t);
    for(int i=h[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==son[u]||v==f[u])continue;
        dfs2(v,v);
    }
}
struct segtree{
    struct TREE{
        int ls,lr,sum,tag;
    }tr[N];
    void build(int root,int ls,int lr){
        tr[root].lr=lr,tr[root].ls=ls,tr[root].tag=-1;
        if(ls==lr){
            return ;
        }
        int mid=(ls+lr)>>1;
        build(lson,ls,mid);
        build(rson,mid+1,lr);
    }
    void update(int root){
        tr[root].sum=tr[lson].sum+tr[rson].sum;
    }
    void pushdown(int root){
        if(!~tr[root].tag)return ;
        else if(tr[root].tag){
            tr[lson].sum=tr[lson].lr-tr[lson].ls+1;
            tr[rson].sum=tr[rson].lr-tr[rson].ls+1;
            tr[lson].tag=1,tr[rson].tag=1;
        }
        else{
            tr[lson].sum=0,tr[rson].sum=0;
            tr[lson].tag=0,tr[rson].tag=0;
        }
        tr[root].tag=-1;
    }
    void change(int root,int ls,int lr,int k){
        if(tr[root].ls>=ls&&tr[root].lr<=lr){
            if(k){
                tr[root].sum=tr[root].lr-tr[root].ls+1;
                tr[root].tag=1;
                return ;
            }
            else{
                tr[root].sum=0,tr[root].tag=0;
                return ;
            }
        }
        pushdown(root);
        int mid=(tr[root].ls+tr[root].lr)>>1;
        if(mid>=ls) change(lson,ls,lr,k);
        if(mid<lr) change(rson,ls,lr,k);
        update(root);
    }
    int query(int root,int ls,int lr){
        if(tr[root].lr<=lr&&tr[root].ls>=ls)return tr[root].sum;
        pushdown(root);
        int res=0;
        int mid=(tr[root].ls+tr[root].lr)>>1;
        if(mid>=ls)res+=query(lson,ls,lr);
        if(mid<lr)res+=query(rson,ls,lr);
        return res;
    }
}t;
void change_path(int x,int y,int k){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        t.change(1,id[top[x]],id[x],k);
        x=f[top[x]];
    }
    if(id[x]==id[y])return ;//注意这里要特判 
    else if(id[x]>id[y])swap(x,y);
    t.change(1,id[x]+1,id[y],k);//注意这里要+1 
}
int query_path(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res+=t.query(1,id[top[x]],id[x]);
        x=f[top[x]];
    }
    if(id[x]==id[y])return res;//注意这里要特判 
    else if(id[x]>id[y])swap(x,y);
    res+=t.query(1,id[x]+1,id[y]);//注意这里要+1 
    return res;
}
//-------------------以上是很板的树剖--------------------
int main(){
    n=read(),q=read();
    for(int i=1;i<=n;++i)fa[i]=i;
    for(int i=1;i<=q;++i){
        int t=read(),u=read(),v=read();
        opt[i]={t,u,v,0,0};//先假设答案为0且区间赋值成0 
        if(opt[i].type==1){
            if(merge(opt[i].u,opt[i].v)) opt[i].val=1;//如果合并成功了,即合并之前,u、v之间没有边,那么这个1操作相当于区间赋1 
        }
        else{
            if(!check(opt[i].u,opt[i].v)) opt[i].ans=-1;//不连通,答案为-1 
        }
    }
    for(int i=1;i<=n;++i){
        if(id[i])continue;//如果i这个点是单独的一颗树,继续dfs 
        dfs1(i,0);
        dfs2(i,i);
    }
    t.build(1,1,n);
    for(int i=1;i<=q;++i){
        if(opt[i].type==1){
            change_path(opt[i].u,opt[i].v,opt[i].val);//区间赋0或1
        }
        else{
            if(~opt[i].ans){//答案不是-1 
                opt[i].ans=query_path(opt[i].u,opt[i].v);//查询路径上的权值和 
            }
        }
    }
    for(int i=1;i<=q;++i){
        if(opt[i].type==2)printf("%d\n",opt[i].ans);
    }
    return 0;
}

此时我们就愉快地通过了本题 \sim