CodeForces Round #112 Div2 165 D. Beard Graph

/*
题目给定一棵树,这棵树很特殊，只有根节点的度可能超过2
有三种操作 
1.把编号为x的边染成黑色
2.把编号为x的边染成白色（此时这条边不可以走）
3.询问x,y之间的距离（不能走到输出-1）

*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=100009;
//**********************************树状数组
struct bit{  
     int c[maxn] ;   
     void init(){  
          memset(c , 0 ,sizeof(c));  
     }  
     int lowbit(int x){  
         return x&(-x);  
     }  
     void add(int x ,int d){ //在x处加上d  
          for( ; x < maxn ; x+=lowbit(x)) c[x]+=d ;   
     }  
     int sum(int x){ //求小于等于x的个数  
          int ans = 0 ;  
          for( ; x>0 ; x-=lowbit(x))  ans +=c[x] ;   
          return ans ;  
     }  
     int getkth1(int k){// 求第K小数模版1  
          int ans = 0 , cnt = 0 , i ;  
          for(i = 20 ; i>=0 ; --i){  
                ans += 1<<i ;  
                if(ans>=maxn||cnt+c[ans]>=k) ans-=1<<i ;  
                else cnt +=c[ans] ;        
          }  
          return ans+1 ;   
     }  
       
        int getkth2(int k){//求第K小数模版2  
            int l=0,r=maxn,mid,f;  
            while(l<r-1)  
            { mid=(l+r)>>1;  
              f=sum(mid);  
                if(f>=k) r=mid;  
                else l=mid;  
            }  
            return r;  
        }  
}tree; 
//****************************************
vector<int> node[maxn];
vector<pair<int,int> > edge;
int degree[maxn],L[maxn],pos[maxn],now,yy,lei[maxn],n,m;
//L[x]表示x和根的距离
//pos[x]表示dfs遍历时的顺序
//yy表示当前遍历的是根的第几个分支
//lei[x]表示x包含在根的第几个分支中
void dfs(int u,int f)
{
	L[u]=L[f]+1;
	pos[u]=now++;
	lei[u]=yy;
	for(int i=0;i<node[u].size();i++)
	{
		int y=node[u][i];
		if(y==f)continue;
		dfs(y,u);
	}
}
int main()
{
	int a,b,c;
	while(scanf("%d",&n)!=EOF)
	{
		tree.init();
		memset(degree,0,sizeof(degree));
		now=1;
		for(int i=1;i<=n;i++)
		{
			node[i].clear();
		}
		edge.clear();
		for(int i=1;i<=n-1;i++)
		{
			scanf("%d%d",&a,&b);
			degree[a]++;
			degree[b]++;
			node[a].push_back(b);
			node[b].push_back(a);
			edge.push_back(make_pair(a,b));
		}
		int root=1;
		for(int i=1;i<=n;i++)
		{
			if(degree[i]>2)
			{
				root=i;
				break;
			}
		}	
		L[root]=0;
		for(int i=0;i<node[root].size();i++)
		{
			yy=node[root][i];
			dfs(yy,root);
		}
		scanf("%d",&m);
		for(int i=0;i<m;i++)
		{
			scanf("%d",&c);
			if(c==3)
			{
				scanf("%d%d",&a,&b);
				if(pos[a]>pos[b])swap(a,b);
				if(a==root)//有一个为根，检查跟到b之间是否有白色的边
				{
					if(tree.sum(pos[b])-tree.sum(pos[lei[b]]-1)==0)
					cout<<L[b]<<endl;
					else 
					cout<<"-1"<<endl;
				}
				else if(lei[a]==lei[b])//属于同一个分支
				{
					if(tree.sum(pos[b])-tree.sum(pos[a])==0)
					cout<<L[b]-L[a]<<endl;
					else 
					cout<<"-1"<<endl;
				}
				else//属于不同的分支，同时检查这两个分支
				{
					if((tree.sum(pos[b])-tree.sum(pos[lei[b]]-1)==0)&&(tree.sum(pos[a])-tree.sum(pos[lei[a]]-1)==0))
					{
						cout<<L[a]+L[b]<<endl;
					}
					else cout<<"-1"<<endl;
				}
			}
			else if(c==2)
			{
				scanf("%d",&a);
				a--;
				int x=max(pos[edge[a].first],pos[edge[a].second]);
				tree.add(x,-1);
			}
			else 
			{
				scanf("%d",&a);
				a--;
				int x=max(pos[edge[a].first],pos[edge[a].second]);
				tree.add(x,1);
			}
		}
	}
 return 0;
}