BZOJ 1086 [SCOI 2005] 왕실 연방 트리 블록

제목: 링크

메서드: 트리 블록

확인:

솔모대에 가서 나무에 올라가기 위해 나무 조각을 배우러 왔는데, 이게 나체문제라고 해서 달려왔어요.

나무가 블록을 나누는 과정은 무엇입니까?

나무 뿌리에서 아래로 돌아가서 검색합니다. 만약에 거슬러 올라가는 노드가 우리가 나누고 싶은 블록의 크기를 초과하면 (a로 설정해도 무방하다) 이 노드를 하나의 블록으로 하고 거슬러 올라가는 이 노드는 이 블록의 임의의 노드와 연결됩니다.

이곳은 분명히 창고로 처리할 수 있다.

그리고 주의해야 할 것은 만약 우리가 제한을 하지 않는다면 어떤 결과가 나타날까요?나누어진 덩어리의 원소를 부스러기로 만들어 마구 나누게 할 것이다.

무슨 제한이죠?

각 노드의 상대적인 창고 밑에 대한 제한입니다.

만약 현재 노드에 있다면, 그는 두 명의 아들이 있다.

왼쪽 아들의 나무에서 찾은 노드 수가 a-1이라면 이때 우리는 오른쪽 아들을 수색한다. 오른쪽 아들을 뿌리로 하는 나무는 길이가 10000인 사슬이라고 가정해도 무방하다.

그러면 분명히 맨 아래의 잎 노드는 왼쪽 아들이 대표하는 자목과 같은 덩어리에 있는데, 이것은 분명히 부스러기로 부서졌다.

그래서 매번 노드를 찾을 때마다 우리는 현재의 창고의 지침을 이 노드의 상대적인 창고 밑바닥으로 삼아야 한다. 그러면 이 문제를 피할 수 있다.

위의 내용과 같이 스스로 보충해 주십시오.

이렇게 하면 끝인가요?

아니요.

마지막 창고에는 아직 많은 점이 남아 있지만 b를 초과하지 않고 우리가 나누어 놓은 블록의 크기도 2b(자체 뇌보)를 초과하지 않기 때문에 창고에 있는 모든 점을 마지막 덩어리에 던져라. 크기는 3b를 초과하지 않고 문제의 요구에 딱 맞다.

코드:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1010
using namespace std;
int sta[N];
int n,b,cnt;
int head[N];
int root[N];
int belong[N];
bool v[N];
int tot,top;
struct node
{
    int from,to,next;
}edge[N<<1];
void init()
{
    memset(head,-1,sizeof(head));
    cnt=1;
}
void edgeadd(int from,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
void dfs(int now)
{
    v[now]=1;
    int bot=top;
    for(int i=head[now];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(v[to])continue;
        dfs(to);
        if(top-bot>=b)
        {
            tot++;
            root[tot]=now;
            do
            {
                belong[sta[top]]=tot; 
                top--;
            }while(top!=bot);
        }
    }
    sta[++top]=now;
}
int main()
{
    init();
    scanf("%d%d",&n,&b);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        edgeadd(x,y);
        edgeadd(y,x);
    }
    dfs(1);
    while(top)
    {
        belong[sta[top--]]=tot;
    }
    cout<<tot<<endl;
    for(int i=1;i<n;i++)cout<<belong[i]<<' ';
    cout<<belong[n]<<endl;
    for(int i=1;i<tot;i++)cout<<root[i]<<' ';
    cout<<root[tot]<<endl; 
}