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 ("");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.