/*
题目给定一棵树,这棵树很特殊,只有根节点的度可能超过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;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include #include #include #include #include #include #include #include #include #define ...
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
今天CF被D恶心到了,写个题解重新整理下思路,(20开始想,25写完暴力代码,1.30才过,优化后的。。 核心思路就是在暴力的基础上进行组合数等差加速。 C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
传送门 题意: 给两个整数u,v,构造一个数组,使得数组的异或和等于u,数组的和等于v 要求构造的数组尽可能的短 思路: 对于每种情况讨论输出即可,注意几种情况的特判 看代码应该能明白 代码: ...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
传送门 题意: The pair of topics
传送门 题意: 给一个数组,然后让你找一个满足题意的排序方式 思路: 先从小到大排序, 拿第一个举例 -2,4,5,5,6,8 要输出的序列应该是每次从前面选一个,然后从后面选一个 -2,8,4,6,5,5 ...#d
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...