COJ 1006 트 리 조작
22276 단어 조작 하 다.
WZJ 의 데이터 구조 (6)
난이도 레벨: D;운행 시간 제한: 1000 ms;실행 공간 제한: 51200 KB;코드 길이 제한: 2000000 B
시험 문제 설명
N 개의 노드 가 없 는 나무 한 그루 를 드 리 겠 습 니 다. 가장자리 사이 에 값 이 있 습 니 다.데이터 구 조 를 설계 하여 다음 과 같은 두 가지 조작 을 진행 하 십시오.
1. 수정: a, b 를 드 리 고 a 조 변 의 가중치 를 b 로 바 꿉 니 다.
2. 질문: a, b 를 드 립 니 다. a 에서 b 경로 까지 의 최대 값, 최소 값 과 가중치 와 a = b 를 출력 하면 "error" 를 출력 합 니 다.
입력
첫 번 째 행 위 는 정수 N 이다.
다음 N - 1 행 위 는 각 줄 마다 3 개의 정수 a, b, c 로 a 에서 b 의 가중치 가 c 인 변 (1 부터 번호) 이 있 음 을 나타 낸다.
N + 1 행 위 는 정수 Q 로 Q 차 조작 을 나타 낸다.
다음 Q 행 위 는 매번 질문 할 때마다 줄 당 3 개의 정수 t, a, b, t = 1 은 질문 을 표시 하고 t = 0 은 수정 을 표시 합 니 다.
출력
매번 질문 에 대해 세 개의 정수, 즉 최대 값, 최소 값 과 가중치 와 a = b 를 출력 하면 'error' 를 출력 합 니 다.
예제 입력
5 1 2 41 4 53 4 62 5 741 1 51 2 50 1 21 1 5
출력 예시
7 4 117 7 77 2 9
기타 설명
1<=N,Q<=50000
1<=c<=1000
문의 중인 1 < = a, b < = N
수정 중인 1 & lt; = a & gt; = N - 1, 1 & gt; = b & gt; = 1000
제목: 나무 사슬 로 나 누 기 귀찮아 LCT 걷 기
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<queue>
6 #include<cstring>
7 #define PAU putchar(' ')
8 #define ENT putchar('
')
9 using namespace std;
10 const int maxn=100000+10,inf=-1u>>1;
11 inline int read(){
12 int x=0,sig=1;char ch=getchar();
13 while(!isdigit(ch)){if(ch=='-')sig=-1;ch=getchar();}
14 while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
15 return x*=sig;
16 }
17 inline void write(int x){
18 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;
19 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;
20 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;
21 }
22 struct node {
23 int x,mi,mx,sm,set;bool rev;
24 node *ch[2],*fa;
25 inline void add_rev_tag(){
26 swap(ch[0],ch[1]);rev^=1;return;
27 }
28 inline void add_set_tag(int a){
29 x=set=a;
30 if(mi!=inf) mi=set;
31 if(mx!=-inf) mx=set;
32 }
33 inline void down(){
34 if(rev){
35 if(ch[0]) ch[0]->add_rev_tag();
36 if(ch[1]) ch[1]->add_rev_tag();
37 rev=0;
38 }
39 if(set){
40 if(ch[0]) ch[0]->add_set_tag(set);
41 if(ch[1]) ch[1]->add_set_tag(set);
42 set=0;
43 }
44 return;
45 }
46 inline void update(){
47 sm=x;mi=inf;mx=-inf;
48 if(ch[0]) sm+=ch[0]->sm,mi=min(mi,ch[0]->mi),mx=max(mx,ch[0]->mx);
49 if(ch[1]) sm+=ch[1]->sm,mi=min(mi,ch[1]->mi),mx=max(mx,ch[1]->mx);
50 if(!x) return;
51 mi=min(x,mi);
52 mx=max(x,mx);
53 return;
54 }
55 }lct[maxn];
56 inline int get_parent(node *x,node *&fa){return (fa=x->fa)?fa->ch[0]==x?0:fa->ch[1]==x?1:-1:-1;}
57 inline void rotate(node *x){
58 int t1,t2;
59 node *fa,*gfa;
60 t1=get_parent(x,fa);
61 t2=get_parent(fa,gfa);
62 if ((fa->ch[t1]=x->ch[t1^1])) fa->ch[t1]->fa=fa;
63 x->ch[t1^1]=fa;fa->fa=x;x->fa=gfa;
64 if (t2!=-1) gfa->ch[t2]=x;
65 fa->update();return;
66 }
67 inline void pushdown(node *x){
68 static node *stack[maxn];
69 int cnt=0;
70 while(1){
71 stack[cnt++]=x;
72 node *fa=x->fa;
73 if (!fa || (fa->ch[0]!=x && fa->ch[1]!=x)) break;
74 x=fa;
75 }
76 while(cnt--) stack[cnt]->down();
77 return;
78 }
79 inline node * splay(node *x){
80 pushdown(x);
81 while(1){
82 int t1,t2;
83 node *fa,*gfa;
84 t1=get_parent(x,fa);
85 if(t1==-1) break;
86 t2=get_parent(fa,gfa);
87 if(t2==-1){
88 rotate(x);break;
89 } else if (t1==t2){
90 rotate(fa);rotate(x);
91 } else{
92 rotate(x);rotate(x);
93 }
94 }
95 x->update();
96 return x;
97 }
98 inline node * access(node *x){
99 node *ret=NULL;
100 while (x) splay(x)->ch[1]=ret,(ret=x)->update(),x=x->fa;
101 return ret;
102 }
103 inline void makeroot(int x){access(lct+x)->add_rev_tag();}
104 inline void link(int u,int v){
105 makeroot(u);splay(lct+u)->fa=lct+v;return;
106 }
107 int n,q;
108 int main(){
109 n=read();
110 int i;
111 int lim=n<<1;
112 for(i=1;i<=lim;i++) {
113 lct[i]=(node){0,inf,-inf,0,0,0};
114 }
115 for(i=1;i<n;i++){
116 int u,v,w;
117 u=read();v=read();
118 link(u,i+n);link(v,i+n);lct[i+n].add_set_tag(read());
119 }
120 q=read();
121 int x,y,c;
122 while(q--){
123 c=read();x=read();y=read();
124 if(c==0) makeroot(x+n),access(x+n+lct)->add_set_tag(y);
125 else{
126 if(x==y){puts("error");continue;}
127 makeroot(x);node*t=access(y+lct);
128 write(t->mx);PAU;write(t->mi);PAU;write(t->sm);ENT;
129 }
130 }
131 return 0;
132 }
수색 하 다.
복제 하 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux 운영 명령 more더 많은 명령, cat 와 유사 한 기능;cat 명령 은 전체 파일 의 내용 을 위 에서 아래로 화면 에 표시 합 니 다.more 명령 은 한 페이지 한 페이지 씩 표 시 됩 니 다. more 명령 은 이전에 파일 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.