(최장 체인) 템플릿 문제

5001 단어
제목 설명 Description은 현재 N개의 결점 두 갈래 나무를 제시하고 이 두 갈래 나무 중 가장 긴 사슬의 길이가 얼마인지 물어보며 1번 결점이 두 갈래 나무의 뿌리임을 보증합니다.
입력 설명 Input Description 입력의 첫 번째 동작은 두 갈래 나무의 결점 수를 위한 정수 N을 포함하고 결점 표시는 1에서 N까지입니다.다음 N행, 이 N행의 i행은 두 개의 정수 l[i], r[i]를 포함하고 결점 i의 왼쪽 아들과 오른쪽 아들의 번호를 나타낸다.만약에 l[i]가 0이면 결점 i에 왼쪽 아들이 없다는 것을 나타내고, 마찬가지로 r[i]가 0이면 오른쪽 아들이 없다는 것을 나타낸다.
출력 설명 Output Description 출력은 두 갈래 나무의 최장 체인 길이를 위한 정수 1개를 포함합니다.
샘플 입력 Sample Input 5 2 3 4 50 6 0 0
샘플 출력 샘플 출력 4
데이터 범위 및 알림 Data Size & Hint [예시 설명] 4-2-1-3-6은 이 두 갈래 나무 중 가장 긴 체인입니다.
【데이터 규모】 10%의 데이터에 대해 N≤10이 있다.40%의 데이터에 대해 N≤100이 있음;50%의 데이터에 대해 N≤1000이 있음;60%의 데이터에 대해 N≤10000; 있음;100%의 데이터에 대해 N≤100000이 있고 나무의 깊이가 32768을 넘지 않도록 보장합니다.
【제시】 두 갈래 나무에 대한 귀속 정의: 두 갈래 나무는 비어 있거나 뿌리 결점, 왼쪽 나무, 오른쪽 나무로 구성되어 있다.왼쪽 나무와 오른쪽 나무는 각각 두 갈래 나무다.뿌리 나무와 두 갈래 나무의 세 가지 주요 차이가 있음을 주의하십시오. 1.나무의 결점 개수는 적어도 1이고 두 갈래 나무의 결점 개수는 0이다.2. 나무에서 결점의 최대 도수는 제한이 없고 두 갈래 나무 결점의 최대 도수는 2이다.3. 나무의 결점은 왼쪽, 오른쪽의 구분이 없고 두 갈래 나무의 결점은 왼쪽, 오른쪽의 구분이 있다.최장 체인에 관하여: 최장 체인은 이 두 갈래 나무 중 가장 긴 간단한 경로, 즉 중복 결점을 거치지 않는 경로이다.두 갈래 나무 중 가장 긴 사슬의 시작, 끝 결점은 모두 잎 결점이라는 것을 쉽게 증명할 수 있다.
우선 제목은 나무 한 그루를 주고 구성할 수 있는 사슬의 최대 길이를 구하라는 뜻이다.우리는 두 개의 연결된 노드의 거리가 1이라는 것을 알 수 있기 때문에 우리는 귀속적인 방법을 운용하여 부모 노드에 연결된 길이의 값을 하위 노드에 부여할 수 있다.즉, 만약에 이런 두 갈래 나무가 있는데 그 중의 한 노드에 두 개의 잎 노드가 연결되어 있다면 우리는 이 두 개의 잎 노드의 값부치가 1이라고 말한다. 이 부 노드와 이 잎 노드가 형성하는 사슬의 길이가 1이라는 것을 나타낸다. 따라서 이 부 노드가 형성하는 사슬의 길이를 가장 크게 하려면 왼쪽 아들 노드의 값과 오른쪽 아들 노드의 값을 더해야 한다. 즉, 이 부 노드가 형성하는 사슬의 최대치이다.이 부노드의 값은 가장 큰 아들 노드의 값+1을 취하여 이 부노드의 부노드와 그 부노드가 구성하는 체인의 최대값을 표시하기 때문에 이 부노드의 값은 2이어야 한다.마지막으로 모든 노드가 구성할 수 있는 최장 체인의 길이를 다시 한 번 검색하고 현재 찾은 최장 체인의 길이를 끊임없이 비교하여 최대치를 찾아 값을 부여한다.
#include 
#include 


int n;
int son[100001][2]={0};
int deep[100001]={0};
int ans;

void find(int a);
int max(int a,int b);
void found(int a);

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d%d",&son[i][0],&son[i][1]);
    if (son[1][0])
        find(son[1][0]);
    if (son[1][1])
        find(son[1][1]);
    for (int i=1;i<=n;i++)
        found(i);
    printf("%d",ans); 

}

void find(int a)
{
    if (son[a][0])
        find(son[a][0]);
    if (son[a][1])
        find(son[a][1]);
    deep[a]=max(deep[son[a][0]],deep[son[a][1]])+1;
    int b=deep[son[a][0]]+deep[son[a][1]];
    if (b>ans)
        ans=b;
}

void found(int a)
{
    int b=deep[son[a][0]]+deep[son[a][1]];
    if (b>ans)
        ans=b;
}

int max(int a,int b)
{
    if (a>b)
        return a;
    else
        return b;
}

좋은 웹페이지 즐겨찾기