hdu 4008 트 리 dp 시간 스탬프 트 리 구조 에서 의 응용

제목 의 대의:
N 개의 노드 가 있 는 나 무 를 주 고 Q 번 질문 을 한다. 매번 두 개의 점 을 주 는 레이 블 X 와 Y 를 물 어 볼 때마다 X 를 뿌리 로 하 는 상황 에서 Y 의 아들 중 레이 블 이 가장 작은 아들 의 레이 블 과 Y 의 자손 중 레이 블 이 가장 작은 것 을 수출 하 라 고 요구한다.
입력 시 첫 줄 입력 테스트 그룹 수 case
그리고 각 그룹 마다 N 과 Q 를 입력 하 세 요.
그리고 N - 1 쪽 을 입력 하고,
마지막 으로 Q 조 조회 수 대 X 와 Y 를 입력 하 십시오.
Sample input：
1
7 3
1 2
1 5
2 3
2 4
5 6
5 7
1 2
5 3
3 2
Sample output：
3 3
No answer!
1 1
 
제목 분석:
이 문 제 는 가장 좋 은 문 제 를 해결 하 는 것 이 분명 하 다. 동태 계획 은 바로 이런 문 제 를 해결 하 는 좋 은 방법 이다. 먼저 간단 한 방향 에서 출발 하여 주어진 노드 의 아들 중에서 가장 작은 것 을 요구한다. 나무 구조 이 고 뿌리 가 고정 되 지 않 기 때문에 이 노드 와 연 결 된 점 은 모두 이 노드 의 아버지 일 수 있 기 때문에 우 리 는 동태 계획 을 할 때 배열 f 를 설정 할 수 있다.[vertrix][2]배열 아래 에 표 시 된 첫 번 째 표 시 는 현재 노드 의 레이 블 을 나타 내 고 두 번 째 표 시 는 0 으로 최소 연결 노드 의 레이 블 을 나타 낸다. 1 은 작은 연결 노드 의 레이 블 을 나타 낸다. 한 번 에 옮 겨 다 니 는 비 교 를 통 해 최소 연결 노드 레이 블 과 작은 연결 노드 레이 블 을 계산 할 수 있다. 매번 에 최소 연결 노드 가 주어진 노드 의 아버지 인지 판단 하면 된다. 만약 에 그렇지 않 으 면예, 그러면 가장 작은 인접 노드 는 가장 작은 자식 노드 입 니 다. 만약 에 그렇다면 작은 인접 노드 는 바로 원 하 는 것 입 니 다.
그렇다면 관건 적 인 문 제 는 어떻게 해 야 현재 뿌리 가 X 인 상황 에서 가장 작은 연결 노드 가 주어진 노드 의 아버지 인지 판단 할 수 있 습 니까?
저 희 는 tarjan 알고리즘 의 깊이 우선 검색 에 표 시 된 시간 스탬프 의 예비 처리 방법 을 참고 하여 이 문 제 를 효과적으로 해결 할 수 있 습 니 다. 구체 적 인 조작 은 다음 과 같 습 니 다.
우 리 는 최소 연결 노드 레이 블 을 Z 로 설정 했다.
처음에는 기본 1 을 루트 노드 로 하고 깊이 우선 검색 순서에 따라 시간 스탬프 dfn [vertrix] 를 표시 하 며 하위 트 리 의 자손 노드 의 최대 시간 스탬프 back [vertrix] 를 기록 합 니 다.그러면 시간 스탬프 는 반드시 하나의 성질 을 만족 시 킬 것 이다. 즉, 부모 노드 의 시간 스탬프 dfn 은 자손 노드 dfn 보다 작 고 자손 노드 의 시간 스탬프 는 반드시 부모 노드 back 보다 크 지 않다 는 것 이다. 그러면 우 리 는 이러한 성질 에 따라 판단 할 수 있다. 만약 에 X 노드 의 시간 스탬프 가 현재 검색 트 리 의 뿌리 가 뿌리 인 경우 Z 의 서브 트 리 에 있 으 면 X 노드 가 뿌리 로 변 할 때 Z 는 Y 노드 의 아버지 이다.그렇지 않 으 면 X 노드 가 하위 트 리 에서 의 판단 은 시간 스탬프 가 dfn [Z] 에 있 는 지 판단 해 야 합 니 다. back [Z] 와 함께 하면 됩 니 다.
상대 적 으로 어 려 운 것:
주어진 루트 X 의 전제 에서 지정 Y 의 최소 자손 레이 블 을 구 합 니 다.
사실은 비슷 한 사고 로 구 해 를 할 수 있 습 니 다. 배열 dp [vertrix] [2] 를 설정 하고 두 번 째 작은 표 시 를 0 과 1 로 표시 한 배열 로 최소 자손 과 차 작은 자손 을 저장 할 수 있 습 니 다. 마찬가지 로 이전의 시간 스탬프 를 이용 하여 예비 처 리 를 할 수 있 습 니 다.
전이 방정식 은 다음 과 같다.
V 는 현재 루트 아래 u 의 하위 노드 로 모든 하위 노드 v:
           temp = min ( v , dp[v][0] );
            if ( dp[u][0] > temp )
            {
                dp[u][1] = dp[u][0];
                dp[u][0] = temp;
                loc[u] = v;
            }
            else if ( dp[u][1] > temp )
                dp[u][1] = temp;
 
그러면 나머지 는 모든 조회 에 대한 답변 입 니 다.
다음 과 같은 몇 가지 상황 으로 나 눌 수 있다.
1. 현재 뿌리 가 1 인 경우 X 는 Y 의 자나무 에 있 고 Y 가 1 일 때 X 가 최소 자손 이 있 는 자나무 에 있 는 지 판단 하고 loc [vertrix] 로 최소 자손 이 있 는 자나무 의 뿌리 를 기록 합 니 다 ( Y 의 아들 중 하나) 라 는 레이 블 은 X 가 이 나무 에 있다 면 Y 의 막내 자손 은 X 가 뿌리 인 상태 에서 Y 와 한 그루 의 나무 나 Y 의 조상 이 없 을 수 밖 에 없다. 그러면 Y 의 막내 자손 은 다음 의 작은 자손 이 고 그렇지 않 으 면 막내 자손 이다.
2. 현재 뿌리 가 1 인 경우 X 가 Y 의 하위 트 리 에 있 고 Y 가 1 이 아 닐 때 X 가 뿌리 일 때 1 Y 의 자손 이 분명 하 므 로 Y 의 막내 자손 은 반드시 1 이다.
3. 현재 뿌리 가 1 인 경우 X 가 Y 의 하위 나무 에 없 으 면 X 가 뿌리 로 변 한 후에 Y 의 하위 나무 구 조 를 바 꾸 지 않 기 때문에 Y 의 최소 자손 은 변 하지 않 습 니 다.
다음은 ac 코드:
 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 100077
#define INF 0xfffffff

using namespace std;

int t , n , q;
int maxn;

struct
{
    int v,next;
}e[MAX<<1];

int head[MAX];
int cc = 0;

void add ( int u , int v )
{
    e[cc].v = v ;
    e[cc].next = head[u];
    head[u] = cc++;
}

int dfn[MAX] , step = 0;
int back[MAX];
int dp[MAX][2];
int f[MAX][2];
int loc[MAX];
int father[MAX];
//bool used[MAX];

void dfs ( int u , int fa )
{
    dfn[u] = ++step;
    back[u] = dfn[u];
    father[u] = fa;
    dp[u][0] = dp[u][1] = f[u][0] = f[u][1] = INF;
    for ( int i = head[u] ; i != -1 ; i = e[i].next )
    {
        int v = e[i].v;
        if ( v != fa )
        {
            if ( f[u][0] > v )
            {
                f[u][1] = f[u][0];
                f[u][0] = v;
            }
            else if ( f[u][1] > v )
            {
                f[u][1] = v;
            }
            dfs ( v , u );
            int temp;
            temp = min ( v , dp[v][0] );
            if ( dp[u][0] > temp )
            {
                dp[u][1] = dp[u][0];
                dp[u][0] = temp;
                loc[u] = v;
            }
            else if ( dp[u][1] > temp )
                dp[u][1] = temp;
            back[u] = max ( back[v], back[u] );
        }
    }
}

int main ( )
{
    scanf ( "%d" , &t );
    int x , y;
    while ( t-- )
    {
        memset ( head , -1 , sizeof( head ));
        cc = 0;
        step = 0;
        scanf ( "%d%d" , &n , &q );
        for ( int i = 1; i <= n-1 ; i++ )
        {
            scanf ( "%d%d" , &x , &y );
            add ( x , y );
            add ( y , x );
        }
       // memset ( used , 0 , sizeof ( used ) );
        dfs ( 1 , -1 );
        //cout << "sadasdadas"<< endl;
        for ( int i = 1 ; i <= q ; i++ )
        {
            scanf ( "%d%d" , &x , &y );
            int ans1 , ans2;
            if ( dfn[x] > dfn[y] && dfn[x] <= back[y] )
            {
                if ( y == 1 )
                {
                    if ( dfn[x] >= dfn[f[y][0]] && dfn[x] <= back[f[y][0]])
                        ans1 = f[y][1];
                    else ans1 = f[y][0];
                    if ( dfn[x] >= dfn[loc[y]] && dfn[x] <= back[loc[y]] )
                        ans2 = dp[y][1];
                    else ans2 = dp[y][0];
                }
                else
                {
                    if ( dfn[x] >= dfn[f[y][0]] && dfn[x] <= back[f[y][0]] )
                        ans1 = min ( father[y] ,f[y][1] );
                    else ans1 = min ( f[y][0] , father[y] );
                    ans2 = 1;
                }
            }
            else
            {
                ans1 = f[y][0];
                ans2 = dp[y][0];
            }
            if ( ans1 == INF || ans2 == INF ) printf ( "no answers!
");
            else printf ( "%d %d
" , ans1 , ans2 );
        }
        puts ("");
    }
}