데이터 구조Search

문제 설명
불쌍 한 비비 가 집에 돌아 오 자마자 자신의 휴대 전 화 를 잃 어 버 린 것 을 발견 하고 뒤 돌아 서서 자신의 휴대 전 화 를 검색 하기 로 했다.지금 우 리 는 비비 의 집 이 이 진 트 리 의 뿌리 에 있다 고 가정 한다.비비 의 마음 속 에 모든 노드 에 하나의 가중치 x 가 있 는데 그의 마음 속 에서 이 노드 로 가면 자신의 핸드폰 을 찾 을 수 있 을 것 이 라 고 예감 하 는 정 도 를 나타 낸다 (그의 예감 은 전혀 정확 하지 않 지만).비비 가 한 노드 에 도 착 했 을 때 이 노드 에 검색 하지 않 은 아들 노드 가 있 으 면 비비 가 검색 하지 않 은 아들 노드 로 가서 검색 을 하고 그렇지 않 으 면 아버지 노드 로 돌아간다.만약 에 특정한 노드 가 검색 되 지 않 은 두 개의 아들 노드 를 가지 고 있다 면 비 비 는 가중치 가 큰 아들 노드 를 먼저 검색 할 것 이다.만약 에 비비 가 한 노드 에서 다른 노드 에 도착 하 는 데 1 단위 의 시간 이 필요 하 다 고 가정 하고 노드 를 검색 하 는 시간 은 무시 합 니 다. 그러면 비비 의 핸드폰 이 k 번호 의 노드 에 있 을 때 그 는 몇 단위 의 시간 이 걸 려 야 핸드폰 을 찾 을 수 있 습 니까?
★ 데이터 입력 입력 첫 번 째 행위 의 정수 n (1 ≤ n ≤ 100000) 은 나무의 노드 수 를 나타 내 고 나무의 뿌리 번 호 는 항상 1 이다.다음 n - 1 줄, 각 줄 에 두 개의 정수 p, x (1 ≤ x ≤ 100).번호 가 i 인 노드 를 대표 하 는 아버지 노드 p 와 가중치 x.여기 i 는 2 에서 n 까지 입 니 다.데 이 터 는 입력 한 p 가 현재 i 보다 적 고 서로 형제 인 두 노드 의 가중치 x 가 다르다 는 것 을 보증 합 니 다.n + 1 행 하나의 정수 m (1 ≤ m ≤ n) 는 문의 조 수 를 나타 낸다.n + 2 줄 에는 m 개의 정수 가 있 고 각 정수 ki (1 ≤ ki ≤ n) 는 이 그룹 을 대표 하여 문의 중인 핸드폰 의 위 치 를 나타 낸다.
★ 데이터 출력 m 줄, 줄 마다 하나의 정수, 비비 가 핸드폰 을 찾 는 데 걸 리 는 단위 시간 수량 을 나타 낸다.
예제 입력
출력 예시
31 201 3031 2 3
0 3 1
문제 풀이 의 사고 방향.
두 갈래 나무 dfs 한 번 걷 기
주의해 야 할 것 은 모든 노드 에 대해 노드 진입 과 탈퇴 노드 step 는 모두 + 1 해 야 한 다 는 것 이다.
 
code

#include 
#include 
#include <string.h>

struct Node
{
    Node(){}
    int weight;
    int step;
    int left;
    int right;
};

Node *arr = NULL;
int step = 0;

void dfs(int index)
{
    arr[index].step = step;
    ++step;
    if(arr[index].left==0)
    {
        
    }
    else if(arr[index].right==0)
    {
        dfs(arr[index].left);
    }
    else if(arr[arr[index].left].weight > arr[arr[index].right].weight)
    {
        dfs(arr[index].left);
        dfs(arr[index].right);
    }
    else
    {
        dfs(arr[index].right);
        dfs(arr[index].left);
    }
    ++step;
}

int main()
{
    int i;
    int n,m,k;
    scanf("%d",&n);
    arr = (Node *)malloc(sizeof(Node)*(n+1));
    memset(arr,0,sizeof(Node)*(n+1));
    
    int fa_index,weight;
    for(i=2;i<=n;i++)
    {
        scanf("%d %d",&fa_index,&weight);
        if(arr[fa_index].left==NULL)
            arr[fa_index].left = i;
        else // (arr[fa_index].left!=NULL)
            arr[fa_index].right = i;
        arr[i].weight = weight;
    }
    dfs(1);
    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d",&k);
        printf("%d ",arr[k].step);
    }
    
    free(arr);
    return 0;
}

 
다음으로 전송:https://www.cnblogs.com/cbattle/p/7790227.html