[LA 7402] colorful tree 데이터 구조
17687 단어 데이터 구조
원래 의 문제 전송 문 WC 에서 유 여 가 씨 가 추천 한 문 제 는 그 당시 에 많은 동료 들 과 오랫동안 생각 했 는데 어떤 사람 이 괜 찮 은 방법 (그런데 잊 어 버 렸 다.) 을 주 고 유 에 게 메 일 로 물 었 다. 유 는 나 에 게 문 제 를 풀 어 주 었 다. 보고 나 서 야 어떻게 해 야 할 지 대충 알 게 되 었 다.이 문 제 를 통 해 나무 에서 하 는 일 은 직접 서열 에서 하 는 것 보다 더 나 쁘 지 않다 는 것 을 깨 달 았 다.(WC 상영 원 커 뮤 니 케 이 션 을 인용 하고 싶 을 때..................................................................................zgy 신 번 의 한 마디 는 그다지 합 리 적 이지 않 아 보 이 는 이 사실 뒤의 원인 을 잘 설명 했다. "자 나 무 는 n 개 (구간 에 O (n2) 개 만 있다."한 걸음 한 걸음 분석 해 보 자.서술 의 편 의 를 위해 우 리 는 형식 화 된 정 의 를 내 렸 다. 그것 은 이원 그룹 (u, c) 이다. 즉, 뿌리 노드 가 u 인 서브 트 리 의 모든 결점 의 색 을 모두 c 로 수정 하 는 것 이다.통일 을 위해 서 는 모든 결점 의 초기 색상 도 한 번 의 수정 으로 보 는 것 이 좋 습 니 다.한 그루 의 나 무 를 수정 할 때, 우 리 는 폭력 적 으로 이전에 이 나무 에 존 재 했 던 수정 사항 을 순서대로 찾 아 폭력 적 으로 삭제 해 야 한다.분명히 모든 수정 은 u 의 모든 조상 결점 에 영향 을 줄 수 있 지만 어떻게 빠 뜨리 지 않 는 통 계 를 중시 하지 않 습 니까?사실 우 리 는 한 그루 의 나무 에서 같은 색깔 의 점 중 dfs 순서 가 가장 큰 점 이 그것 에 미 치 는 영향 만 고려 하면 된다.이 를 위해 다음 과 같은 방법 을 사용 하 는 것 도 좋 습 니 다. 색깔 이 같은 모든 점 을 dfs 순서 로 배열 하고 a1, a2, a3,...................................................................................................ak 는 뿌리 에 있 는 경로 에 직접적인 영향 을 주면 됩 니 다.이렇게 해서 우 리 는 특정한 색깔 에 대해 dfs 서열 의 가장 큰 점 의 영향 만 을 고려 했다 는 것 을 보증 했다.같은 색상 의 점 집합 과 모든 수 정 된 집합 은 밸 런 스 트 리 로 유지 할 수 있 습 니 다.어떤 점 을 물 을 때 모든 수정 이 그 에 미 친 영향 을 포함 하 는 것 외 에 도 고려 해 야 한다. 만약 에 이 점 이 어떠한 수정 (즉, 수정 한 u 가 하나 도 없다) 에 속 하지 않 는 다 면 우 리 는 그의 실제 색 (이것 은 선분 트 리 를 사용 하여 간단하게 유지 할 수 있다) 을 알 아야 한다. 또한 이런 색 이 서브 트 리 의 특정한 수정 에 나 타 났 는 지 알 아야 한다.(그런 색 의 밸 런 스 트 리 에서 찾 으 면 됩 니 다) 답 을 하나 더 붙 여야 하 는 지 판단 합 니 다. 위의 서술 에 따 르 면 이 문제 가 트 리 의 경로 업데이트 + 단일 조회 로 바 뀌 었 음 을 알 수 있 습 니 다. 정상 인 들 은 이 걸 보면 트 리 체인 분할 + 트 리 배열 을 사용 합 니 다.아니면 엘 시 티 가 해 결 했 나 봐 요.
#include
",t);
fen.clear();
d.clear();
pp=clo=0;
clr(head,0);
clr(hs,0);
clr(son,0);
scanf("%d",&n);
seg.init();
for(int i=1;iint u,v;
scanf("%d%d",&u,&v);
adde(u,v);
adde(v,u);
}
for(int i=1;i<=n;i++){
scanf("%d",&c[i]);
S[i].clear();
}
dfs1(1);
clo=0;
dfs2(1,1);
dfs3(1);
int q;
scanf("%d",&q);
while(q--){
int k,u,nc;
scanf("%d%d",&k,&u);
if(k==0){
scanf("%d",&nc);
modify(u,nc);
}else printf("%d
",fen.sum(u));
}
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
