D. Beard Graph

https://codeforces.com/problemset/problem/165/D

主要是边转点

后面都是简单的线段树维护

我们维护ok标记,val值，黑（1),白（0） 

id.ok=l.ok&r.ok

id.val=l.val+r.val

注意特判如果两个点一样是0,如果dfn[u]+1>dfn[v]就不用询问了直接返回

code

// Problem: Beard Graph
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF165D
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<vector>
using namespace std;
const int N=1e5+9;
int n;
int a[N];
struct edge{int u,v,w;
}ee[N];
vector<edge> e[N];
void add(int u,int v){e[u].push_back({v,u,1});e[v].push_back({u,v,1});
}
int sz[N],fa[N],wc[N],dep[N],dis[N];
void dfs1(int u,int f){fa[u]=f;sz[u]=1;dep[u]=dep[f]+1;for(auto &[x,y,z] : e[u]){if(x==f){dis[u]=z;continue;}if(x!=f){dfs1(x,u);sz[u]+=sz[x];if(sz[x]>sz[wc[u]]){wc[u]=x;}}}
}
int top[N],dfn[N],vistime;
void dfs2(int u,int Top){dfn[u]=++vistime;a[vistime]=dis[u];top[u]=Top;if(wc[u]){dfs2(wc[u],Top);for(auto &[x,y,z] : e[u]){if(x!=wc[u] && x!=fa[u]){dfs2(x,x);}}}
}
//线段树
struct SEG{#define INF (1<<31)#define ll long long#define tl(id) (id<<1)#define tr(id) (id<<1|1)#define li inlinestruct node{int l,r;int ok;ll val;}seg[N<<2];void pushup(node &id,node &l,node &r){id.ok=l.ok&r.ok;id.val=l.val+r.val;}void pushup(int id){pushup(seg[id],seg[tl(id)],seg[tr(id)]);}li int inrange(int L,int R,int l,int r){return l<=L && R<=r;}li int outofrange(int L,int R,int l,int r){return L>r || R<l;}li void build(const int id,int l,int r){seg[id]={l,r};if(l==r){seg[id].val=a[l];seg[id].ok=a[l];return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}li void update(int id,int l,int r,int pos,int v){if(l==r){seg[id].val=v;seg[id].ok=v;return;}int mid=(l+r)>>1;if(mid>=pos){update(tl(id),l,mid,pos,v);}else{update(tr(id),mid+1,r,pos,v);}pushup(id);}li node query(int id,int l,int r){if(seg[id].l>=l && seg[id].r<=r){return seg[id];}else{int mid=(seg[id].l+seg[id].r)>>1;if(mid>=r){return query(tl(id),l,r);}else if(mid<l){return query(tr(id),l,r);}else{node res;node left=query(tl(id),l,r);node right=query(tr(id),l,r);pushup(res,left,right);return res;}}}
}t;
#define node SEG::node
ll ask(int u,int v){ll res=0;while(top[u]!=top[v]){if(dep[top[u]]<dep[top[v]]){swap(u,v);}node tt=t.query(1,dfn[top[u]],dfn[u]);if(!tt.ok){return -1;}else{res+=tt.val;}u=fa[top[u]];}if(dfn[u]>dfn[v]){swap(u,v);}if(dfn[u]+1>dfn[v]){return res;}node tt=t.query(1,dfn[u]+1,dfn[v]);if(!tt.ok){return -1;}else{res+=tt.val;}return res;
}
int main(){cin>>n;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;ee[i]={u,v,1};add(u,v);}dfs1(1,0);dfs2(1,1);t.build(1,1,n);int m;cin>>m;for(int i=1;i<=m;i++){int op;cin>>op;if(op==1){int u;cin>>u;if(dep[ee[u].u]>dep[ee[u].v]){u=ee[u].u;}else{u=ee[u].v;}t.update(1,1,n,dfn[u],1);}else if(op==2){int u;cin>>u;if(dep[ee[u].u]>dep[ee[u].v]){u=ee[u].u;}else{u=ee[u].v;}t.update(1,1,n,dfn[u],0);}else{int u,v;cin>>u>>v;if(u==v){cout<<0<<'\n';}else{cout<<ask(u,v)<<'\n';}}}return 0;
}