DFS+이산+트 리 배열+디 테 일 HDU 5877

HDU 5877 ：http://acm.hdu.edu.cn/showproblem.php?pid=5877
제목:N 개의 점 에 나 무 를 구성 하고 K 를 하나 더 주세요.몇 쌍 의 허약 한 점 을 찾다.점 대 요 구 는 조상 노드 에 아이 노드 를 곱 한 값 이 K 보다 적 으 면 이 조상 아 이 는 점 대 를 허약 점 으로 하 는 것 이다.
 
아,솔직히 나 는 이 문제 가 나무 모양 배열(구간 구 화)과 귀신 의 연관 이 있 는 지 전혀 몰 랐 다...인터넷 의 문 제 를 보지 않 고 나 는 생각 이 나 지 않 는 다 고 표시 했다.
안 타 깝 게 도 내 가 인터넷 의 문 제 를 봐 도 그들의 사 고 를 이해 하지 못 했다.DFS 코드 를 한참 동안 갉 아 먹고 나 서 야 겨우 알 아 보 았 다  어떻게 나무 모양 의 배열 로 이 문 제 를 연락 합 니까?
대련 지역 전 테니스 경기 의 마지막 문제 라 고 합 니 다.
 
또 하 나 는 자신 이 여전히 분 산 된 사용 을 관통 시 키 지 않 았 다 는 점 이다.맵 을 직접 사용 하 는 것 보다 저 는 순환 맵 을 쓰 는 경향 이 있 지만 불편 합 니 다.대부분 맵 으로 이산 작업 을 하 는 것 이 편리 합 니 다.그러나 방금 이산 화 와 템 플 릿 이 발견 되 어 더욱 고 급 스 럽 고 우아 해 졌 다.
둘째,디 테 일 입 니 다.이 문제 가 제시 한 숫자 가 0 일 수 있 는 상황 은 곰 곰 이 생각해 야 합 니 다.2 년 넘 게 코드 를 두 드 렸 는데 항상 이 자모 가 있 습 니 다.수준 은 그래도 향상 시 켜 야 지,너무 경솔 해 서 는 안 된다.
 
이어서 이 문제 의 방향 을 이야기 하 겠 습 니 다.사내 들 이 문 제 를 푸 는 것 은 모두 머리 옆 에 전구 가 켜 지자 깨 달 았 다.그래서 저 같은 소금 에 절 인 생선 은 다른 사람의 블 로 그 를 보면 서 다른 사람 이'아,그 랬 으 면 좋 겠 다.A 가 떨 어 졌 다'는 기분 을 느 꼈 을 때 저 는 그들의 코드 사고방식 을 이해 하지 못 했 을 뿐만 아니 라 어리둥절 한 표정 을 지 으 며 마음 에 큰 상 처 를 입 었 습 니 다.지금 나 는 문 제 를 풀 고,반드시 건강 하고 즐겁게 말 해 야 한다.ㄒoㄒ)/~~
 
사고방식:우 리 는 각 노드 의 값 을 배열 A 로 저장 합 니 다.
     이 문제 가 요구 하 는'허약 한 점 대'수 는 만족 해 야 할 조건 이다.  조상 과 아이 사이 에조건 의 성립 여 부 를 판단 하 는 것 은 바로 판단 이다.   “ A father*A children<=K"  성립 여부.
     우 리 는 이 조건 에 대해 항목 을 옮 기 면 얻 을 수 있다.        “ 조상  <=  "K/(A 아이)"  혹은 “ 아이  <=  K/(A 조상)"
     이 항목 을 옮 긴 후의 등식 에 따라 우 리 는 문 제 를...으로 바 꿀 수 있다.
                         모든 노드 v 를 매 거 하면 우 리 는'K/av'보다 작은 것 을 찾 아야 한다.  ，이 상인 과 같은 모든 조상 노드 의 개수 보다 작 다 는 것 이다.그리고 겹 쳐.
         등가 의 것 은 모든 노드 v 를 매 거 하 는 것 이다.우 리 는'K/A[v]'보다 작은 것 을 찾 아야 한다.  ，즉,이 상인 과 같은 모든 아이들 노드 의 개수 보다 작다.  그리고 겹 쳐.
      만약 우리 가 모든 노드 를 대상 으로 아 이 를 매 거 한다 면 상대 적 으로 좀 번 거 로 울 것 이다.모든 노드 의 아이들 때문에 우 리 는 다시 한 번 찾 아야 알 수 있다.만약 에 우리 가 모든 노드 를 대상 으로 그들의 조상 노드 를 매 거 하면 상대 적 으로 편리 할 것 이다.이것 은 우리 가 뿌리 노드 부터 DFS 를 내 려 가 는 과정 에서 DFS 의 기본 적 인 특성 에 따라 하나의 나무 사슬 을 따라 아래로 검색 한 것 이다.역 추적 법 과 결합 한 후에 우 리 는'변 DFS,계산'의 사상 을 실현 할 수 있 기 때문이다.
     그렇다면 나무 모양 의 배열 은 여기 서 어떻게 나 타 났 을 까?   ——한 점 v 에 대해 어떻게 조건 을 만족 시 키 는 조상 노드 의 개 수 를 찾 습 니까?          태그 역할 을 하 는 트 리 배열 의 전형 적 인 실 용적 인 방법.
    조건 을 충족 시키다  ——즉 조상 점수<=K/A[V]입 니 다.우 리 는 모든 노드 의 값 A[i]와 각 노드 에 대응 하 는 상 을 트 리 배열 에 넣 습 니 다.그러면 DFS 과정 에서 한 노드 를 검색 할 때마다 이 노드 의 값 을 트 리 배열 에 1 로 표시 할 수 있 습 니 다.이 는'이 점 이 나 타 났 다'는 뜻 입 니 다.(add 작업)조상 노드 를 통계 하 는 과정 은 바로 나무 모양 배열 에서 현재 노드 보다 작은 업 체 의 모든 값 을 누적 하여 나무 모양 배열 의 구 와 작업 을 하 는 것 이다.(cal_액 션   나무 사슬 의 DFS 검색 이 끝 난 후에 다시 거 슬러 올 라 가 이 표 시 를 없 애 야 합 니 다.다른 나무 사슬 에 있어 서 이 나무 사슬 은 그 나무 사슬 의 조상 이 아니 라 add 작업 에-1 을 더 하면 됩 니 다.
 
    이산 화 작업.여러 번 틀 렸 고 많은 문제 가 이산 화 위 에 나 타 났 다.
     나무 모양 의 배열 의 크기 가 너무 크 면 터 지기 때문이다.우 리 는 500000 의 크기 만 열 수 있 고 A[i]의 범 위 는 99999999 이기 때문에 이 A[i]들 을 분리 해서 문 제 를 푸 는 데 유리 하 다.
     이 문 제 는?   모든 A[i]를 분 산 했 을 뿐만 아니 라 K/A[i]를 분 산 했 고 동시에 분 산 했 으 며 한 배열 에서 분 산 했 습 니 다.실현 을 위 한 것 이다.  add(A[i]),그리고 calsum( K/A[i] )。 그래서 나무 모양 배열 의 크기 는 n 이 아니 라 2*n 이다.월경 문제 에 주의해 야 한다.
   
    A[i]0 과 같은 디 테 일 한 문제 입 니 다.
    A[i}이 0 일 때 K/A[i]를 계산 할 수 없 기 때문에 오류 가 발생 할 수 있 으 니 주의해 야 합 니 다.어찌 할 까요?우리 가 앞에서 토론 한 적 이 있 는데,점 수 는 업 데 이 트 를 위 한 것 이 고,상 가 는 화 해 를 위 한 것 이다.그러나 A[i]가 0 일 때 모든 하위 노드 는 조건 을 만족시킨다.그래서 우 리 는 그것 을-1 로 나 눌 수 없다.무한대 로 비 춰 야 지.
 
이것 은 제 가 만년 BUG 를 찾 은 후에 드디어 A 가 떨 어 진 코드 입 니 다.하지만 뒤에 제 수정 과 조판 을 거 친 후에 다른 큰 남자 들 의 코드 를 올 리 겠 습 니 다.그들의 생각 은 더욱 뚜렷 하고 직관 적 입 니 다.제 블 로그 의 생각 을 보 는 것 이 좋 습 니 다.코드 는 두 번 째 것 을 보 는 것 이 좋 습 니 다~ 
내 쓰레기 코드:       맵 으로 이산 하 다.이곳 의 pos 배열 은 DFS 에서 아무 소 용이 없다.맵 의 분 리 를 편리 하 게 하기 위해 서 이다.

#include"bits/stdc++.h"
using namespace std;
#define inf 100009
#define INF 999999999
#define loop(x,y,z) for(x=y;xedge[inf];   // 
int node[inf];  //  
ll pos[inf*2];    //     k/node[i]
mapm;
int c[2*inf];     //    
ll ans;         //    
int book[inf];  //    ，       

void init()
{
    int i;
    loop(i,1,n+1)edge[i].clear();
    m.clear();
    memset(c,0,sizeof c);
    memset(book,0,sizeof book);
    ans=0;
}
int lowbit(int i)
{
    return i&-i;
}
int cal_sum(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=c[i];
        i-=lowbit(i);
    }
    return sum;
}
void add(int i,int t)
{
    while(i<=2*n)
    {
        c[i]+=t;
        i+=lowbit(i);
    }
}

void dfs(int u)
{
    ll t=node[u]?m[k/node[u]]:2*inf-10;       //         
    ans+=cal_sum(t);
    int len=edge[u].size(),i;//printf("%d
",m[pos[u]]);
    add(m[node[u]],1);
    loop(i,0,len)
    {
        int v=edge[u][i];
        dfs(v);
    }
    add(m[node[u]],-1);
}

int main()
{
    int i,j,T,root;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d%lld",&n,&k);

        loop(i,1,n+1)
        {
            scanf("%d",&node[i]); //       
            if(node[i])
                pos[i]=k/node[i];       //    k/node[i]
            else pos[i]=-1;
            pos[i+n]=node[i];
        }
        //    
        sort(pos+1,pos+1+n+n);
        j=0;
        loop(i,1,2*n+1)
        {
            if(pos[i]!=pos[i-1])j++;
            m[pos[i]]=j;
        }

        loop(i,1,n)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            book[v]=1;
        }

        loop(i,1,n+1)if(!book[i]){root=i;break;}    //  

        dfs(root);
        printf("%lld
",ans);

    }
    return 0;
}

 
 
다른 고급 코드:  템 플 릿 으로 분 산 됩 니 다.분 산 된 분 산 된 표 는 바로 pos 배열 입 니 다.pos 배열 의 앞 n 개 는 노드 값 의 분 산 된 것 이 고 뒤의 n 개 는 상업 가치 의 분 산 된 것 입 니 다.그 러 니까 DFS 쪽 은 U+n 이 고 U 이 고 이해 해.
 
 

#include 
#include 
#include 
#include 
#include 
#include 
#define ll __int64
using  namespace std;
#define inf 100009
#define INF 999999999
#define loop(x,y,z) for(x=y;xedge[inf];
ll k,ans;
ll pos[inf*2],li[inf*2];

void init()
{
    //m.clear();
    int i;
    loop(i,1,n+1)edge[i].clear();
    memset(c,0,sizeof c);
    memset(book,0,sizeof book);
    ans=0;
}
int lowbit(int i)
{
    return i&-i;
}
int cal_sum(int i)
{
  int sum=0;
  while(i>0){
    sum+=c[i];
    i-=lowbit(i);
  }
  return sum;
}
void add(int i,int t)
{
  while(i<=2*n){
    c[i]+=t;
    i+=lowbit(i);
  }
}

void dfs(int u){
  ans+=cal_sum(pos[u+n]);//             
  add(pos[u], 1);
  for(int i=0; i