점 분할 치료 템 플 릿 문제

제목 설명 n 개의 점 이 있 는 나 무 를 지정 하여 트 리 의 거리 가 k 인 점 이 존재 하 는 지 물 어 봅 니 다.입 출력 형식 입력 형식: n, m 다음 n - 1 개의 변 a, b, c 는 a 에서 b 까지 길이 가 c 인 경 로 를 설명 합 니 다. 다음 m 줄 마다 K 출력 형식 을 물 습 니 다. K 줄 마다 하나의 답 을 출력 할 때 출력 'AYE' 가 존재 합 니 다. 그렇지 않 으 면 출력 'NAY' (따옴표 포함 되 지 않 음)입 출력 샘플 입 출력 샘플 1: 2, 1, 12, 2 출력 샘플 1: AYE 설명 30% 의 데이터 n ≤ 100 대 60% 의 데이터 n ≤ 1000, m ≤ 50 대 100% 의 데이터 n ≤ 10000, m ≤ 100, c ≤ 1000, K ≤ 10000000
문 제 를 관찰 하 는 것 은 분명 하 다. 이것 은 점 분 치 의 틀 문제 이다.그럼 분할 치료 방법 으로 해결 합 시다.그러나 점 분 치 는 어떤 방법 일 까?우선 개인 적 으로 점 분 치 는 나 무 를 계속 나 누 어 처리 하 는 방법 이다.나 무 를 나 누 려 면 나 무 를 몇 부분 으로 나 누 어 처리 해 야 한다.우 리 는 어떤 점 을 선택해 서 분할 해 야 합 니까?빠 른 배열 처럼 선택 한 '중심 점' 이 좋 지 않 으 면 빠 른 배열 의 복잡 도 는 O (n ^ 2) 에 달 할 수 있 고 점 분할 치료 에서 분 치 점 이 점 을 선택 하면 복잡 도 는 O (n) 로 변 할 수 있다.물론 빨리 배열 하 는 과정 에서 하나의 숫자 로 검색 을 해서 선택 한 숫자 가 반드시 중간 값 이 라 고 보장 하 지 는 않 지만 사람들 은 무 작위 로 숫자 를 찾 는 방법 을 선택 하여 복잡 도가 비교적 낮은 상황 에서 보장 할 수도 있다.
나무의 중심: n 개의 노드 가 없 는 나무 에 대해 점 을 찾 아 나 무 를 이 점 을 뿌리 가 있 는 나무 로 만 들 때 가장 큰 나무의 결 점 이 가장 작다.다시 말 하면 이 점 을 삭제 한 후 가장 큰 연결 블록의 결점 수가 가장 작 으 면 이 점 이 나무의 중심 이다.나무의 중심: 가장자리 에 권력 이 있 는 나 무 를 주 고 나무의 점 을 구하 여 이 점 을 나무의 다른 결점 의 가장 먼 거리 에서 가장 가 깝 게 합 니 다.
우 리 는 만약 우리 가 나무의 중심 을 얻 을 수 있다 면, 우 리 는 나무의 중심 을 분할 점 으로 하여, 잘 린 후의 모든 자 나 무 를 가능 한 한 평균 적 으로 할 수 있다 는 것 을 발견 했다. 왜냐하면 이 점 의 최대 자 나무의 결 점 이 가장 작 기 때문이다.그러면 점 분 치 의 첫 번 째 중요 한 조작 은 바로 나무 (또는 잘 린 나무) 의 중심 위 치 를 구 하 는 것 이다.
해법: 하나의 결점 을 뿌리 로 선택 하고 뿌리 없 는 나 무 를 뿌리 있 는 나무 로 만 든 다음 에 f [i] 를 설치 하여 i 를 뿌리 로 하 는 서브 나무의 결점 개 수 를 표시 합 니 다.f [i] =Σf[j] (j∈s[i]) + 1 。프로그램 구현 은 간단 합 니 다. DFS 한 번 만 있 으 면 뿌리 없 는 나무 에서 뿌리 있 는 나 무 를 돌 리 는 동시에 동기 화 계산 하면 됩 니 다.사실 결점 i 를 삭제 한 후에 가장 큰 연결 블록 은 몇 개의 결점 이 있 습 니까?결점 i 의 서브 트 리 중 가장 큰 것 은 max {f [j]} 개의 결점 이 있 고, i 의 '위쪽 서브 트 리' 에는 n - f [i] 개의 결점 이 있다.
물론, 우 리 는 f [i] 배열 을 사용 하여 노드 가 i 를 뿌리 로 하 는 서브 트 리 의 노드 개 수 를 저장 할 수 있 습 니 다.이렇게 되면 효율 이 상대 적 으로 떨 어 질 수 있 기 때문이다.또한 하나의 배열 기록 g [i] 를 추가 하여 i 를 뿌리 로 하 는 가장 큰 하위 나무의 결산 점 개 수 를 표시 하면 우 리 는 g [i] = max {f [j]} (j 는 i 의 아들) 을 얻 은 다음 에 g [i] 와 i 의 조상 과 그 나머지 부분의 결산 점 개 수 를 비교 할 수 있다 (즉 i 를 뿌리 로 하 는 하위 나 무 를 제외 한 다른 나무의 부분).i 를 뿌리 로 하 는 최대 하위 나무의 결점 개 수 를 나타 낸다.모든 g [i] 를 비교 하여 DFS (깊이 우선 검색) 과정 에서 비교 하여 현재 트 리 의 중심 을 얻 을 수 있 습 니 다.
이어서 우 리 는 분 치 의 두 번 째 중요 한 부분 을 시작 했다.점 분 치 는 용 척 된 사상 을 운용 하 였 다.우리 가 점 치 료 를 사용 할 때 중심 을 찾 은 후에 이 를 분점 으로 삼 아 먼저 분점 부터 모든 점 을 옮 겨 다 니 며 이 나무의 모든 점 거리 분점 의 크기 를 계산 한 다음 에 두 조합 을 기록 했다. 다시 말 하면 이 나 무 는 실제 적 으로 분점 을 뿌리 로 하 는 것 이다.다른 모든 결점 은 분 치 점 에 직접 연 결 된 나무 이다. 즉, 이 나 무 는 깊이 가 2 인 나무 로 간주 된다.그리고 모든 점 에서 분 치 점 까지 의 거 리 를 이용 하여 모든 점 (분 치 점 자체 포함) 간 의 거 리 를 계산 하고 배열 에 넣는다.물론 결점 간 의 거 리 를 구하 면 정렬 방법 을 활용 할 수 있다. 그러면 문제 가 설정 한 최대 범 위 를 초과 하 는 상황 을 더욱 빨리 걸 러 내 고 연산 횟수 를 줄 일 수 있다.이렇게 하면 자나무 의 결점 거리 가 길 어 지 는 경우 가 있다.예 를 들 어 한 그루 의 나무 에 결산 점 거리 분할 점 dis [i] 가 있 는데 그의 아들 의 결산 점 거리 분할 점 dis [j] 는 그들 사이 의 거 리 는 dis [j] - dis [i] 여야 한다. 그러나 우 리 는 그것 을 깊이 가 2 인 다 진 나무 로 보 는 상황 을 통 해 그들의 거 리 를 dis [j] + dis [i] 로 계산한다.그래서 우 리 는 이러한 dis [j] + dis [i] 의 상황 을 삭제 해 야 한다. 그러면 우 리 는 분할 점 을 선택 하여 이 나 무 를 몇 부분 으로 나 누 었 다.그러면 우 리 는 분 치 점 을 삭제 하고 이 나무의 중심 을 다시 구 한 다음 에 분 치 점 으로 거 리 를 계속 구 하면 dis [j] - dis [i] 의 상황 을 구 할 수 있다.물론 이런 상황 을 구 했 을 때 는 이미 최초의 분점 과 관계 가 없 었 다.그렇다면 우 리 는 어떻게 같은 나무의 결점 간 의 거 리 를 삭제 합 니까?분명 한 것 은 우리 가 분 치 점 에서 시작 하여 그의 아들 i 에서 분 치 점 까지 의 거 리 를 미리 기록 한 다음 에 분 치 점 에서 다른 결점 까지 의 거 리 를 구 하 는 것 처럼 결점 i 의 모든 아들 에서 결점 i 까지 의 거 리 를 구하 고 2 를 추가 하 는 것 이다.×dis [i], 그리고 얻 은 이 거 리 를 배열 에서 삭제 합 니 다.이렇게 하면 같은 나무의 결점 간 의 중복 상황 을 삭제 할 수 있다.분 치 점 을 삭제 한 후에 이 분 치 점 의 모든 서브 트 리 에 중심 을 두 고 계속 반복 하면 답 을 얻 을 수 있다.코드 는 다음 과 같 습 니 다:

#include 

using namespace std;

const int maxn=10010;
bool vis[maxn];
int treest[maxn],h[maxn],remind[maxn],deep[maxn],dis[maxn];
int n,m,root,tot,sum;
int num[10000010];
struct edge{
    int to,next,value;
}e[maxn<<1];

inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while ((c!='-')&&((c<'0')||(c>'9')))
        c=getchar();
    if (c=='-')
        f=-1,c=getchar();
    while ((c>='0')&&(c<='9'))
    {
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}

void getroot(int ,int );
void qsort(int ,int );
void divide(int );
void getdeep(int ,int );

int main()
{
    n=read();
    m=read();
    for (int i=1,u,v,w;i0]=sum=n;
    getroot(1,0);
    divide(root);
    for (int i=1;i<=m;i++)
    {
        int p;
        p=read();
        if (num[p])
            printf("AYE
");
        else
            printf("NAY
");
    }
    return 0;   
}

void getdeep(int now,int fa)
{
    dis[++tot]=deep[now];
    for (int jump=h[now];jump;jump=e[jump].next)
    {
        int t=e[jump].to;
        if (t==fa||vis[t])
            continue;
        deep[t]=deep[now]+e[jump].value;
        getdeep(t,now);
    }
    return ;
}

void calculate(int now,int dep,int add)
{
    tot=0;
    deep[now]=dep;
    getdeep(now,0);
    for (int i=1;i<=tot;i++)
        for (int j=1;j<=tot;j++)
            num[dis[i]+dis[j]]+=add;
    return ;
}

void divide(int now)
{
    calculate(now,0,1);
    vis[now]=true;
    for (int jump=h[now];jump;jump=e[jump].next)
    {
        int t=e[jump].to;
        if (vis[t])
            continue;
        calculate(t,e[jump].value,-1);
        root=0;
        sum=remind[t];
        getroot(t,0);
        divide(root);
    }
    return ;
}

void getroot(int now,int fa)
{
    remind[now]=1;
    treest[now]=0;
        for (int jump=h[now];jump;jump=e[jump].next)
    {
        int t=e[jump].to;
        if (t==fa||dis[t])
            continue;
        getroot(t,now);
        remind[now]+=remind[t];
        treest[now]=max(treest[now],remind[t]);
    }
    treest[now]=max(treest[now],sum-remind[now]);
    if (treest[now]return ;
}

void qsort(int l,int r)
{
    int a=l,b=r;
    int c=dis[(a+b)/2];
    while (a<=b)
    {
        while (dis[a]while (dis[b]>c)
            b--;
        if (a<=b)
        {
            int f=dis[a];
            dis[a]=dis[b];
            dis[b]=f;
            a++;
            b--;
        }
    }
    if (aif (lreturn ;
}