• 欢迎光临~

[[AHOI2005] 航线规划]([AHOI2005] 航线规划 - 洛谷)

``````#include<bits/stdc++.h>
#define pii pair<int,int>
#define mid (l+r>>1)
#define lson rt<<1
#define rson rt<<1|1
#define ls l,mid,lson
#define rs mid+1,r,rson
using namespace std;
const int N=1e6+5;
int n,m;
struct node{
int u,v;
bool f;
}edge[N];
int tot1;
struct node1{
int op,u,v;
}ope[N];
map<pii,bool> mp;
struct node2{
int nxt,v,val;
}tree[N<<1];
}
int fa[N],depth[N],sz[N],son[N];
void dfs1(int x){
sz[x]=1;
if(!sz[y=tree[i].v]&&!mp[pii(x,y)])
depth[y]=depth[x]+1,fa[y]=x,dfs1(y),sz[x]+=sz[y],(sz[son[x]]<sz[y])&&(son[x]=y);
}
int dfn[N],tot,top[N];
void dfs2(int x,int tp){
dfn[x]=++tot,top[x]=tp;
if(son[x]) dfs2(son[x],tp);
if((y=tree[i].v)==fa[x]||y==son[x]||fa[y]!=x) continue;
dfs2(y,y);
}
}
struct node4{
int sum;
bool flag;
}tr[N<<1];
void up(int rt){
tr[rt].sum=tr[lson].sum+tr[rson].sum;
}
void build(int l,int r,int rt){
if(l==r){
tr[rt].sum=1;
return;
}
build(ls),build(rs),up(rt);
}
void down(int rt){
tr[lson].flag=tr[rson].flag=1,tr[rt].flag=tr[lson].sum=tr[rson].sum=0;
}
void update(int l,int r,int rt,int a,int b){
if(a<=l&&r<=b){
tr[rt].flag=1,tr[rt].sum=0;
return;
}
if(tr[rt].flag) down(rt);
if(mid>=a) update(ls,a,b);
if(mid<b) update(rs,a,b);
up(rt);
}
void modify(int x,int y){
if(x==y) return;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
update(1,n,1,dfn[top[x]],dfn[x]),x=fa[top[x]];
}
int t1=max(dfn[x],dfn[y]),t2=min(dfn[x],dfn[y]);
if(t1==t2) return;
update(1,n,1,t2+1,t1);
}
int get(int l,int r,int rt,int a,int b){
if(a<=l&&r<=b) return tr[rt].sum;
int ans=0;
if(tr[rt].flag) down(rt);
if(mid>=a) ans+=get(ls,a,b);
if(mid<b) ans+=get(rs,a,b);
up(rt);
return ans;
}
if(x==y) return 0;
int ans=0;
while(top[x]!=top[y]){
if(depth[top[x]]<depth[top[y]]) swap(x,y);
ans+=get(1,n,1,dfn[top[x]],dfn[x]),x=fa[top[x]];
}
int t1=max(dfn[x],dfn[y]),t2=min(dfn[x],dfn[y]);
if(t1==t2) return ans;
return ans+get(1,n,1,t2+1,t1);
}
int ans[N];
int main(){
scanf("%d%d",&n,&m);
while(scanf("%d",&ope[++tot1].op)&&ope[tot1].op!=-1){
scanf("%d%d",&ope[tot1].u,&ope[tot1].v);
if(!ope[tot1].op) mp[pii(ope[tot1].u,ope[tot1].v)]=mp[pii(ope[tot1].v,ope[tot1].u)]=true;
} --tot1;
depth[1]=1,dfs1(1),dfs2(1,1);
build(1,n,1);
for(int i=1;i<=m;++i) if(!mp[pii(edge[i].u,edge[i].v)]&&fa[edge[i].u]!=edge[i].v&&fa[edge[i].v]!=edge[i].u) modify(edge[i].u,edge[i].v);
for(int i=tot1;i;--i){
if(ope[i].op==0) modify(ope[i].u,ope[i].v);