树剖题不用多说，一开始所有黑边的权值是-1，若有修改白边的操作，就把白边的值赋为100000。
之后查询边权之和时，如果和大于1000000，就肯定存在白边，直接输出-1。
//做法：树剖，一开始黑边边权全设为1，若有修改白边，设为100000 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node{ int nxt,to,val,from; }edge[maxn*4]; int head[maxn],cnt; void add(int x,int y,int v){ edge[++cnt].nxt=head[x]; edge[cnt].from=x; edge[cnt].to=y; edge[cnt].val=v; head[x]=cnt; } int n,m; int x,y; int opt,num; int dep[maxn],fa[maxn],size[maxn],son[maxn],w[maxn]; void dfs1(int x,int f){ fa[x]=f; size[x]=1; dep[x]=dep[f]+1; int maxson=-1; for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(v==fa[x]) continue; w[v]=edge[i].val; dfs1(v,x); size[x]+=size[v]; if(size[v]>maxson){ maxson=size[v]; son[x]=v; } } } int id[maxn],top[maxn],va[maxn],Time; void dfs2(int x,int topf){ top[x]=topf; id[x]=++Time; va[id[x]]=w[x]; if(!son[x]) return; dfs2(son[x],topf); for(int i=head[x];i;i=edge[i].nxt){ int v=edge[i].to; if(v==fa[x]||v==son[x]) continue; dfs2(v,v); } } struct nod{ int l,r; long long sum; int lazy; }tree[maxn*4]; void build(int now,int l,int r){ tree[now].l=l,tree[now].r=r,tree[now].lazy=-1; if(l==r){ tree[now].sum=va[l]; return; } int mid=(l+r)>>1; build(now<<1,l,mid); build(now<<1|1,mid+1,r); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; } void pushdown(int now){ if(tree[now].lazy!=-1){ tree[now<<1].sum=(tree[now<<1].r-tree[now<<1].l+1)*tree[now].lazy; tree[now<<1|1].sum=(tree[now<<1|1].r-tree[now<<1|1].r+1)*tree[now].lazy; tree[now<<1].lazy=tree[now].lazy; tree[now<<1|1].lazy=tree[now].lazy; tree[now].lazy=-1; } } void update(int now,int l,int r,int v){ if(tree[now].l>=l&&tree[now].r<=r){ tree[now].sum=(tree[now].r-tree[now].l+1)*v; tree[now].lazy=v; return; } pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; if(l<=mid) update(now<<1,l,r,v); if(r>mid) update(now<<1|1,l,r,v); tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum; } long long query(int now,int l,int r){ if(tree[now].l>=l&&tree[now].r<=r) return tree[now].sum; pushdown(now); int mid=(tree[now].l+tree[now].r)>>1; long long val=0; if(l<=mid) val+=query(now<<1,l,r); if(r>mid) val+=query(now<<1|1,l,r); return val; } long long link(int x,int y){ long long ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y); ans+=query(1,id[y]+1,id[x]); return ans; } int main(){ scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); add(x,y,1);add(y,x,1); } scanf("%d",&m); dfs1(1,0); dfs2(1,1); build(1,1,n); for(int i=1;i<=m;i++){ scanf("%d",&opt); if(opt==2){ scanf("%d",&num); int s=edge[num*2].from; int t=edge[num*2].to; if(dep[s]>dep[t]) swap(s,t); update(1,id[t],id[t],1000000); } else if(opt==1){ scanf("%d",&num); int s=edge[num*2].from; int t=edge[num*2].to; if(dep[s]>dep[t]) swap(s,t); update(1,id[t],id[t],1); } else{ scanf("%d%d",&x,&y); if(link(x,y)>=1000000) printf("-1 "); else printf("%lld ",link(x,y)); } } return 0; }