[codevs] 1814 최장 체인 나무의 지름

링크
제목 설명 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 5
0 6
0 0
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이고 두 갈래 나무의 결점 개수는 0이다

나무 중 결점의 최대 도수는 제한이 없고 두 갈래 나무 결점의 최대 도수는 2이다

나무의 결점은 왼쪽, 오른쪽의 구분이 없고, 두 갈래 나무의 결점은 왼쪽, 오른쪽의 구분이 있다..

최장 체인 정보:
최장 체인은 이 두 갈래 나무 중 가장 긴 간단한 경로, 즉 중복 결점을 거치지 않는 경로이다.두 갈래 나무 중 가장 긴 사슬의 시작, 끝 결점은 모두 잎 결점이라는 것을 쉽게 증명할 수 있다.
나무의 직경의 누드 문제...
먼저 아무 점이나 골라서 검색을 시작하고 가장 먼 곳을 찾아라.다시 그 지점부터 뒤져서 가장 먼 지점까지 뒤져라.이 두 점은 바로 나무의 지름의 시작점과 끝점이다.bfs를 두 번 할 수도 있고 dfs를 두 번 할 수도 있습니다.
코드는 다음과 같습니다.

#include
#include
#include
#include
using namespace std;

const int SZ=100000+10;

int first[SZ],nxt[SZ<<1];
struct edge{
    int from,to;
}es[SZ<<1];
int tot=0,n;

void build(int ff,int tt)
{
    es[++tot]=(edge){ff,tt};
    nxt[tot]=first[ff];
    first[ff]=tot;
}

int ans=0,pos;
void dfs(int u,int f,int val)
{
    if(val>ans)
    {
        ans=val;
        pos=u;
    }
    for(int i=first[u];i!=-1;i=nxt[i])
    {
        int v=es[i].to;
        if(v==f) continue;
        dfs(v,u,val+1);
    }
}

int main()
{
     memset(first,-1,sizeof(first));
     int n;
     scanf("%d",&n);
     for(int i=1;i<=n;i++)
     {
        int l,r;
        scanf("%d%d",&l,&r);
        if(l) build(l,i),build(i,l);
        if(r) build(r,i),build(i,r);
     }
     dfs(1,1,0);
     ans=0;
     dfs(pos,1,0);
     cout<return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

HDU 3631 Shortest Path(Floyd + 플러그인)

제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[codevs] 1814 최장 체인 나무의 지름

좋은 웹페이지 즐겨찾기