首页 > 代码库 > BZOJ 3319 黑白树
BZOJ 3319 黑白树
3319: 黑白树
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 557 Solved: 194
[Submit][Status][Discuss]
Description
给定一棵树,边的颜色为黑或白,初始时全部为白色。维护两个操作:
1.查询u到根路径上的第一条黑色边的标号。
2.将u到v 路径上的所有边的颜色设为黑色。
Notice:这棵树的根节点为1Input
第一行两个数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
Sample Output
0
2
1
HINT
对于 100% 的数据:n,m<=10^6
看见这道题之后似乎可以用树剖来打但是$10^6$的数据范围显然对于树剖的巨大常数$O(nlogn)$是无法承受的
这题在$HZOJ$上的数据极其坑爹,卡几乎所有正解。。。网上找的$BZOJ$标程都$TLE$了。。。
然而不卡暴力..不卡暴力...暴力...(╯‵□′)╯︵┻━┻
目测数据是个菊花图。。。深度极其的浅导致依靠子树大小来减少时间消耗的正解被时间与深度相关的暴力程序力压。。。
最后弃疗怂一波用暴力A掉了这题QwQ
暴力袋马如下:
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 7 const int MAXE=2000010; 8 const int MAXV=1000010; 9 10 struct Edge{ 11 int from; 12 int to; 13 int id; 14 Edge* next; 15 }; 16 17 Edge E[MAXE]; 18 Edge* head[MAXV]; 19 Edge* top=E; 20 21 int n; 22 int m; 23 int id[MAXV]; 24 int prt[MAXV]; 25 int deep[MAXV]; 26 bool color[MAXV]; 27 28 void Initialize(); 29 void Insert(int,int,int); 30 int Query(int); 31 void DFS(int,int,int,int); 32 void Modify(int,int); 33 34 int main(){ 35 int a,b,c; 36 Initialize(); 37 DFS(1,0,0,1); 38 for(int i=0;i<m;i++){ 39 scanf("%d%d",&a,&b); 40 if(a==1){ 41 printf("%d\n",Query(b)); 42 } 43 else if(a==2){ 44 scanf("%d",&c); 45 Modify(b,c); 46 } 47 } 48 return 0; 49 } 50 51 void Modify(int x,int y){ 52 while(x!=y){ 53 if(deep[x]<deep[y]) 54 std::swap(x,y); 55 color[id[x]]=true; 56 x=prt[x]; 57 } 58 } 59 60 int Query(int x){ 61 while(x!=1){ 62 if(color[id[x]]) 63 return id[x]; 64 else 65 x=prt[x]; 66 } 67 return 0; 68 } 69 70 void DFS(int root,int prt,int deep,int id){ 71 ::id[root]=id; 72 ::prt[root]=prt; 73 ::deep[root]=deep; 74 for(Edge* i=head[root];i!=NULL;i=i->next){ 75 if(i->to==prt) 76 continue; 77 DFS(i->to,root,deep+1,i->id); 78 } 79 } 80 81 void Initialize(){ 82 int a,b; 83 scanf("%d%d",&n,&m); 84 for(int i=1;i<n;i++){ 85 scanf("%d%d",&a,&b); 86 Insert(a,b,i); 87 Insert(b,a,i); 88 } 89 } 90 91 inline void Insert(int from,int to,int id){ 92 top->id=id; 93 top->to=to; 94 top->from=from; 95 top->next=head[from]; 96 head[from]=top; 97 top++; 98 }
彪乘袋马可能会在我的GitHub Repository里更新QwQ
BZOJ 3319 黑白树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。