题解：P14411 [JOISC 2015] 道路建设 / Road Development
本题解采用了P11361 [NOIP2024] 编辑字符串的一篇高赞题解的形式，采用循序渐进的方法带领读者走向正解。
若你完全没有思路：
::::info[提示]
想一想：两种操作的本质分别是什么？
::::
::::success[答案]
第一种操作：查询
第二种操作：判断
有一些想法后：
::::info[提示]
若要建图，图是什么样的？
::::
::::success[答案]
在任意时刻，图为森林且不存在环。
::::info[证明]
对于第一种操作，若原先不存在
对于第二种操作，它根本不会建边。
:::: 成功分析透彻题目后： ::::info[提示] 如何维护上述两种操作？ :::: ::::success[答案] 对于第一种操作，前面已经说过，在任意时刻图都是森林且不存在环，那么它们路径唯一，带修改且要维护路径一般常用树链剖分。
具体做法：若原先
对于第二种操作，用一个并查集维护连通性即可。 :::: ::::warning[注意] 由于图可能是森林，所以会有很多棵树，要对所有的树都进行树链剖分。 ::::
好的，你已经成功切掉了这道蓝题。 ::::success[AC code]
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mp(i,j) make_pair(i,j)
const int N=3e5+10;
int n,Q;
struct node{
int op,x,y,val;
}q[N];
int ans[N],F[N];
int findx(int x){
if(x!=F[x])F[x]=findx(F[x]);
return F[x];
}
vector<int> g[N];
int dfn[N],num=0,son[N],siz[N],dep[N],top[N],f[N];
inline void dfs(int u,int fa){
son[u]=0;siz[u]=1;
dep[u]=dep[fa]+1;f[u]=fa;
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
siz[u]+=siz[v];
if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
}
}
inline void dfs2(int x,int topx){
top[x]=topx;
dfn[x]=++num;
if(!son[x])return;
dfs2(son[x],topx);
for(int y:g[x]){
if(y!=son[x]&&y!=f[x])dfs2(y,y);
}
return;
}
struct BIT{
int t[N<<2],tag[N<<2];
inline void push_up(int x){
t[x]=t[x*2]+t[x*2+1];
return;
}
inline void push_down(int l,int r,int x){
if(tag[x]!=-1){
int mid=l+r>>1,k=tag[x];
tag[x*2]=k;tag[x*2+1]=k;
t[x*2]=(mid-l+1)*k;t[x*2+1]=(r-mid)*k;
tag[x]=-1;
}
return;
}
inline void build(int l,int r,int x){
tag[x]=-1;t[x]=0;
if(l==r)return;
int mid=l+r>>1;
build(l,mid,x*2);
build(mid+1,r,x*2+1);
return;
}
inline void update(int L,int R,int l,int r,int x,int k){
if(L<=l&&r<=R){
t[x]=(r-l+1)*k;
tag[x]=k;
return;
}
push_down(l,r,x);
int mid=l+r>>1;
if(L<=mid)update(L,R,l,mid,x*2,k);
if(R>mid)update(L,R,mid+1,r,x*2+1,k);
push_up(x);
return;
}
inline int ask(int L,int R,int l,int r,int x){
if(L<=l&&r<=R)return t[x];
push_down(l,r,x);
int mid=l+r>>1,res=0;
if(L<=mid)res+=ask(L,R,l,mid,x*2);
if(R>mid)res+=ask(L,R,mid+1,r,x*2+1);
return res;
}
}tree;
inline void update_range(int x,int y,int k){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
tree.update(max(1ll,dfn[top[x]]-1),dfn[x]-1,1,n,1,k);
x=f[top[x]];
}
if(x==y)return;
else{
if(dep[x]>dep[y])swap(x,y);
tree.update(dfn[x],dfn[y]-1,1,n,1,k);
}
return;
}
inline int ask_range(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
res+=tree.ask(max(1ll,dfn[top[x]]-1),dfn[x]-1,1,n,1);
//cout<<"x="<<x<<" top["<<x<<"]="<<top[x]<<" dfn[top[x]]-1="<<dfn[top[x]]-1<<" dfn[x]-1="<<dfn[x]-1<<"\n";
x=f[top[x]];
}
if(x==y)return res;
if(dep[x]>dep[y])swap(x,y);
res+=tree.ask(dfn[x],dfn[y]-1,1,n,1);
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>Q;
for(int i=1;i<=n;i++)F[i]=i;
for(int i=1;i<=Q;i++){
cin>>q[i].op>>q[i].x>>q[i].y;
int fu=findx(q[i].x),fv=findx(q[i].y);
//cout<<"i="<<i<<" fu="<<fu<<" fv="<<fv<<"\n";
if(q[i].op==1){
if(fu==fv)q[i].val=0;//本身就联通不需要加边
else{
F[fu]=fv;q[i].val=1;//不联通，加边然后改成1，查询时查询有多少个1即可
g[q[i].x].push_back(q[i].y);
g[q[i].y].push_back(q[i].x);
//cout<<"u="<<q[i].x<<" v="<<q[i].y<<"\n";
}
}
else if(fu!=fv&&q[i].op==2)ans[i]=-1;
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
dfs(i,0);
dfs2(i,i);
}
}
//for(int i=1;i<=n;i++)cout<<"dfn["<<i<<"]="<<dfn[i]<<" ";cout<<"\n";
for(int i=1;i<=Q;i++){
if(q[i].op==1){
update_range(q[i].x,q[i].y,q[i].val);
//cout<<"i="<<i<<" val="<<q[i].val<<"\n";
}
else{
if(ans[i]==-1)continue;
else ans[i]=ask_range(q[i].x,q[i].y);
}
}
for(int i=1;i<=Q;i++)if(q[i].op==2)cout<<ans[i]<<"\n";
return 0;
}
/*3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3*/
:::: 若对你有帮助，也许可以给我点个赞？