POJ 1741 - TRE [밸 런 스 트 리]
8965 단어 POJ데이터 구조밸 런 스 트 리 트 랩
Give a tree with n vertices,each edge has a length(positive integer less than 1001). Define dist(u,v)=The min distance between node u and v. Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k. Write a program that will count how many pairs which are valid for a given tree.
해제
제목 설명 은 다음 과 같 습 니 다. 나무 한 그루 를 주 고 K 를 정 합 니 다. 이 나무의 점 대 (u, v) 의 개 수 를 구하 고 u, v 의 거 리 는 K 보다 작 습 니 다.이 문 제 는 비교적 정상 적 인 표기 법 은 점 점 점 이지 만 본 고 는 33951 점 이 고 33979 점 이 없 기 때문에 여기 서 균형 트 리 로 하 는 방법 을 소개 합 니 다. 우리 가 가장 유지 하고 싶 은 것 은 무엇 입 니까?우 리 는 모든 나무 에 있 는 모든 노드 에서 하위 나무 뿌리 노드 까지 의 거 리 를 가장 지 키 고 싶 습 니 다. 만약 에 우리 가 이 정 보 를 지 킬 수 있다 면 하위 나무 뿌리의 거 리 는 K 와 같은 개수 보다 작 을 수 있 습 니 다. 그러나 또 다른 상황 은 u, v 가 각각 뿌리 노드 의 두 개의 나무 에 있 습 니 다. 이런 상황 은 그 중의 한 개의 나무 중의 노드 를 매 거 해 야 합 니 다.이 노드 에서 루트 노드 까지 의 거 리 를 d 로 가정 한 다음 에 다른 하위 트 리 에서 루트 노드 의 거 리 를 K - d 와 같은 노드 개수 보다 작 게 찾 습 니 다.그러나 이 과정 은 두 그루 의 나 무 를 매 거 하고 그 중의 한 그루 의 나무 중의 모든 노드 를 매 거 하 는 것 과 관련 되 어 있어 복잡 도가 너무 높다.어떻게 개선 합 니까?먼저 두 개의 Treap 을 합병 하 는 방법 을 소개 해 야 합 니 다. 계발 식 합병: 노드 총수 n 이 상수 라면 이러한 합병 에 대해 노드 수가 적은 Treap 중의 요 소 를 하나씩 노드 수가 큰 Treap 에 추가 하고 모든 Treap 을 한 그루 로 합 치 는 복잡 도 는 O (nlogn) 입 니 다.증명 도 분명 하 다. 모든 노드 에 대해 합병 에 참가 할 때마다 그 가 있 는 Treap 의 노드 수 는 * 2 이다. 그러면 최종 Treap 의 노드 수 는 n 이기 때문에 logn 의 합병 에 가장 많이 참가 하고 모든 노드 가 이 렇 기 때문에 전체적인 복잡 도 는 O (nlogn) 이다.계발 식 합병 이 있 으 면 우 리 는 두 개의 Treap 의 합병 을 신속하게 실현 할 수 있 습 니 다. 그래서 이 문제 에 대해 모든 노드 가 최대 로 logn 회 합병 되 는 성질 을 이용 하여 모든 노드 에 Treap 을 만들어 서 이 를 뿌리 로 하 는 서브 트 리 에서 그의 거 리 를 유지 할 수 있 습 니 다. 그리고 합병 의 총 복잡 도 는 O (nlogn) 이기 때문에 충분히 받 아들 일 수 있 습 니 다.정 답 을 누적 하면 하위 트 리 와 뿌리 노드 가 있 는 Treap 을 직접 합 쳐 다른 하위 트 리 에 정 답 을 누적 할 수 있 습 니 다.하위 트 리 를 먼저 유지 해 야 하기 때문에 아래 에서 위로 나 무 를 옮 겨 다 녀 야 하 며 DFS 의 천연 바닥 에서 위로 향 하 는 성질 을 이용 하여 구현 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:
#includef)rot(p,d^1);
}
p->maintain();
}
int get_n(pnode p,int key){
if(p==null)return 0;
p->pushdown();
if(p->key==key)return p->ch[0]->s+p->cnt;
if(p->key>key)return get_n(p->ch[0],key);
else return get_n(p->ch[1],key)+p->ch[0]->s+p->cnt;
}
void print(pnode p){
p->pushdown();
if(p==null)return;
print(p->ch[0]);
for(int i=1;i<=p->cnt;i++)c[++c[0]]=p->key;
print(p->ch[1]);
}
pnode merge(pnode p1,pnode p2){
c[0]=0;
if(p1->s>p2->s)swap(p1,p2);
print(p1);
for(int i=1;i<=c[0];i++)ans+=get_n(p2,K-c[i]);
for(int i=1;i<=c[0];i++)insert(p2,c[i]);
return p2;
}
void print_Treap(pnode p){
if(p==null)return;
p->pushdown();
print_Treap(p->ch[0]);
for(int i=1;i<=p->cnt;i++)printf("%d ",p->key);
print_Treap(p->ch[1]);
}
pnode dfs(int x){
vis[x]=0;pnode p=newnode(0);
for(int j=lnk[x];j;j=nxt[j]) if(vis[son[j]]){
pnode p2=dfs(son[j]);
p2->tag+=w[j];
p=merge(p2,p);
}
return p;
}
void add(int x,int y,int z){
nxt[++tot]=lnk[x];son[tot]=y;w[tot]=z;lnk[x]=tot;
}
int main(){
scanf("%d%d",&n,&K);
null->ch[0]=null->ch[1]=null;null->key=null->s=null->cnt=null->tag=0;
while(n||K){
tot=0;memset(lnk,0,sizeof(lnk));memset(vis,1,sizeof(vis));
for(int i=1,x,y,z;i"%d%d%d",&x,&y,&z),add(x,y,z),add(y,x,z);
ans=0;len=treap;
dfs(1);
printf("%d
",ans);
scanf("%d%d",&n,&K);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Sparse Table을 아십니까? 나는 알고 있다.Sparse Table을 지금 배웠으므로, 메모를 겸해 씁니다. 불변의 수열의 임의의 구간에 대한 최소치/최대치를, 전처리 $O(N\log N)$, 쿼리 마다 $O(1)$ 로 구하는 데이터 구조입니다. 숫자 열의 값...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
