首页 > 代码库 > BZOJ 3319 黑白树
BZOJ 3319 黑白树
题面:
3319: 黑白树
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 554 Solved: 192
[Submit][Status][Discuss]
Description
给定一棵树,边的颜色为黑或白,初始时全部为白色。维护两个操作:
1.查询u到根路径上的第一条黑色边的标号。
2.将u到v 路径上的所有边的颜色设为黑色。
Notice:这棵树的根节点为1
Input
第一行两个数n,m分别表示点数和操作数。
接下来n-? 1行,每行2个数u,v.表示一条u到v的边。
接下来m行,每行为以下格式:
1 v 表示第一个操作
2 v u 表示第二种操作
Output
对于每个询问,输出相应答案。如果不存在,输出0。
Sample Input
5 4
1 2
1 3
2 4
2 5
1 2
2 2 3
1 3
1 4
1 2
1 3
2 4
2 5
1 2
2 2 3
1 3
1 4
Sample Output
0
2
1
2
1
HINT
对于 100% 的数据:n,m<=10^6
Source
DFS求出每个点父亲,之后暴力修改即可。
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 #define maxn 1000001 5 struct node 6 { 7 int u,v,nex; 8 }edge[maxn<<1]; 9 int cnt,head[maxn]; 10 int depth[maxn],fa[maxn],num[maxn]; 11 bool book[maxn],col[maxn]; 12 void add(int u,int v) 13 { 14 edge[++cnt]=(node){u,v,head[u]}; 15 head[u]=cnt; 16 } 17 void dfs_make(int u,int f) 18 { 19 int v; 20 book[u]=true; 21 for(int i=head[u];i;i=edge[i].nex) 22 { 23 v=edge[i].v; 24 if(book[v]) 25 continue; 26 depth[v]=depth[u]+1; 27 fa[v]=u; 28 num[v]=(i+1)/2; 29 dfs_make(v,u); 30 } 31 } 32 int query(int u) 33 { 34 while(u!=0&&!col[num[u]])u=fa[u]; 35 return u==0?0:num[u]; 36 } 37 void update(int x,int y) 38 { 39 if(depth[x]>depth[y]) 40 x^=y^=x^=y; 41 while(depth[x]!=depth[y]) 42 { 43 col[num[y]]=true; 44 y=fa[y]; 45 } 46 if(x==y) 47 return ; 48 while(x!=y) 49 { 50 col[num[x]]=true; 51 col[num[y]]=true; 52 x=fa[x]; 53 y=fa[y]; 54 } 55 } 56 int n,m; 57 int main() 58 { 59 int x,y,z; 60 scanf("%d%d",&n,&m); 61 for(int i=1;i<n;i++) 62 { 63 scanf("%d%d",&x,&y); 64 add(x,y); 65 add(y,x); 66 } 67 dfs_make(1,0); 68 for(int i=1;i<=m;i++) 69 { 70 scanf("%d%d",&x,&y); 71 if(x==1) 72 printf("%d\n",query(y)); 73 else 74 { 75 scanf("%d",&z); 76 update(y,z); 77 } 78 } 79 }
BZOJ 3319 黑白树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。