题解：P14411 [JOISC 2015] 道路建设 / Road Development
形式化题意
给你
-
1 u v。若u 和v 点之间不存在路径，则在两点之间建一条边，边权有贡献；否则不将路径上的边权计算在贡献中。 -
2 u v。若两点不联通，输出-1，否则输出两点路径上有贡献的边的数量。
思路
先看一会，发现需要判断连通性，所以并查集是肯定少不了的。
画图发现，对于操作一，如果两点之间存在路径，我们并不会删除原来的边，也不会添加新边；如果不存在路径，我们也只会建一条边，两点所属的联通块就会合并，两个联通块的点就存在路径。
所以我们再往下推导，不难发现全部操作完后的图是不存在环的，那不就是树吗！
再看操作，有修改和查询，就不难想到用树链剖分来维护。具体来说，操作一就是分两种情况：联通，就将路径贡献变为
所以整道题的思路就出来了：用并查集维护连通性，离线建出树（也不一定是树，也可能是森林），再用树链剖分维护修改和查询。
代码比较长，码风有点奇怪。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10,N=5e5+10;
struct SegTree{
struct node{
int l,r,w,tag;
};
V<node>a;
SegTree(int _n):a(_n*4+2){}
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((a[x].l+a[x].r)>>1)
#define push_up(x) (a[(x)].w=a[ls((x))].w+a[rs((x))].w)
void build(int x,int l,int r){
a[x].l=l;a[x].r=r;a[x].tag=INF;
if(l==r)return;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
push_up(x);
}
void addtag(int x,int w){
a[x].tag=w;
a[x].w=(a[x].r-a[x].l+1)*w;
}
void push_down(int x){
if(a[x].tag!=INF){
addtag(ls(x),a[x].tag);
addtag(rs(x),a[x].tag);
a[x].tag=INF;
}
}
void update(int x,int L,int R,int w){
if(a[x].l>=L&&a[x].r<=R){
addtag(x,w);
return;
}
push_down(x);
if(L<=mid) update(ls(x),L,R,w);
if(R>mid) update(rs(x),L,R,w);
push_up(x);
}
int query(int x,int L,int R){
if(a[x].l>=L&&a[x].r<=R) return a[x].w;
push_down(x);
if(R<=mid) return query(ls(x),L,R);
else if(L>mid) return query(rs(x),L,R);
else return query(ls(x),L,R)+query(rs(x),L,R);
}
#undef ls
#undef rs
#undef mid
#undef push_up
};
struct DSU{
V<int>fa;
DSU(int _n):fa(_n+2){
iota(fa.begin(),fa.end(),0);
}
int fin(int x){
while(x^fa[x]) x=fa[x]=fa[fa[x]];
return x;
}
bool is_same(int u,int v){
return fin(u)==fin(v);
}
void merge(int u,int v){
u=fin(u);v=fin(v);
if(u==v) return;
fa[u]=v;
}
};
V<int>e[N];
int dep[N],siz[N],son[N],fa[N],top[N],id[N];
int num=0;
void dfs1(int u,int fat){
fa[u]=fat;siz[u]=1;
dep[u]=dep[fat]+1;
for(auto v:e[u]){
if(v==fat)continue;
dfs1(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v]) son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;id[u]=++num;
if(!son[u]) return;
dfs2(son[u],tp);
for(auto v:e[u]){
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
void update(SegTree &lls,int u,int v,int w){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
lls.update(1,id[top[u]],id[u],w);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) lls.update(1,id[u]+1,id[v],w);
}
int query(SegTree &lls,int u,int v){
int ans=0;
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ans+=lls.query(1,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) ans+=lls.query(1,id[u]+1,id[v]);
return ans;
}
struct QUE{
int op,u,v,val,ans;
};
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n,q;cin>>n>>q;
V<QUE>que(q+1);
SegTree lls(n+1);lls.build(1,1,n);
DSU bcj(n+1);
FOR(i,1,q){
int &op=que[i].op,&u=que[i].u,&v=que[i].v;
cin>>op>>u>>v;
if(op&1){
if(!bcj.is_same(u,v)){
bcj.merge(u,v);
e[u].pb(v);e[v].pb(u);
que[i].val=1;
}
}else{
if(!bcj.is_same(u,v)){
que[i].ans=-1;
}
}
}
FOR(i,1,n){
if(!id[i]) dfs1(i,0),dfs2(i,i);
}
FOR(i,1,q){
int op=que[i].op,u=que[i].u,v=que[i].v,ans=que[i].ans,val=que[i].val;
if(op&1) update(lls,u,v,val);
else{
if(ans==-1) cout<<ans<<"\n";
else cout<<query(lls,u,v)<<"\n";
}
}
return 0;
}