트리에서 검색

Question

N 개의 꼭지점이 1에서 N까지 번호가 매겨진 트리가 주어진 경우, 정점 1은 트리의 루트입니다. 각 정점에는 정수 가중치가 지정됩니다. 제거 연산은 임의의 정점 u를 근간으로하는 하위 트리를 제거 할 수 있습니다. 나머지 정점의 총중량 (값의 합)이 최대가되도록 제거 작업을 사용해야합니다. 예 :

     1 
       / \ 
        1  -1 (Remove) 
       /  \ 
    (Remove) -1   -1 

so2 무게가 이전보다 커지도록 제거 작업이 허용됩니다.

트리의 노드가 3 개 이상의 분기를 가질 수 있으므로이 알고리즘을 사용하는 문제를 어떻게 처리 할 것인가?

내 접근 방법 : 우선은 무게를 발견 각 노드 즉

   -1 
      / \ 
       0  -2 
      /  \ 
      -1   -1 

코드 :

static int search(int a,ArrayList<Integer>[] som){ 
      int sum=0;   
      check[a]=true; 
      for(int j=0;j<som[a].size();j++){ 
       weight[a] = value[a]; 
      if(!check[som[a].get(j)]) 
      { 

      weight[a]+= search(som[a].get(j),som); 
      } 
     } 
     return weight[a]; 


} 

내가 할 수있는 동적 프로그래밍 것,이 후 접근하는 방법을 모른다 유용하게 사용하려면 일부 알고리즘이나 방법을 제공하십시오.

여기

역학의 어떤 종류를 사용할 수 있습니다

Answer 1

는 이제

d[i] - maximum sum for subtree starting from vertex i 

을 가정 해 봅시다 그래서

DFS 동안 정점 (무게와 동일)

을 유지하면서 계산됩니다

d[i] = max(0, a[i] + those children of vertex i whose d[] > 0) 

예를 들어 나무 d는 다음과 같습니다.

  2(5) 
     / \ 
      1(2) 0(4) 
     /  \ 
     0(1)   0(3) 

브래킷 번호는 주문

입니다.