HDU - 1502 Anniversary party [트리 dp 시작]

전송문//나무 한 그루, 약간의 권한, 아들과 아버지가 동시에 선택할 수 없음, 얻을 수 있는 최대치가 얼마냐고 묻는다.//이것이 바로 나무형 dp 입문 문제입니다.그래서 방정식은 비교적 쓰기 쉽다.dp[x][0]는 이 점을 선택하지 않는 것을 대표하고 dp[x]는 이 점을 선택한다.dp[i][1] += dp[j][0]; (j는 i의 아들) dp[i][0]+=max(dp[j][0], dp[j][1]);(동일)
그래서 노크를 시작할 수 있습니다. 디테일을 잘 처리하면 됩니다. 구체적인 처리는 코드를 보십시오.
AC Code

const int maxn = 6e3+5;
int dp[maxn][2];
vector<int>g[maxn];
void dfs(int u,int fa)
{
    for(int i=0;iint to = g[u][i];
        if(to == fa) continue;
        dfs(to,u);
    }
    int len = g[u].size();  //       ,         ,        .
    for(int i=0;i 1 || fa == -1);i++){
        int to = g[u][i];
        if(fa == to) continue;
        dp[u][1] += dp[to][0];
        dp[u][0] += max(dp[to][0],dp[to][1]);
    }
}
void solve()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++) g[i].clear();
        Fill(dp,0);
        for(int i=1;i<=n;i++) scanf("%d",&dp[i][1]);
        int u,v;
        while(~scanf("%d%d",&u,&v) && u && v){
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1,-1);
        printf("%d
",max(dp[1][1],dp[1][0]));
    }
}

이것은 나무형 dp의 시작이라고 할 수 있죠. 여기서 사나이가 말한 고전적인 나무형 dp의 제목을 참고해 봤는데...
몇 가지 대표적인 질문을 열거해 보세요.
1: 나무 한 그루의 각 노드에 권한을 부여하여 부모 노드와 하위 노드가 동시에 얻을 수 있는 최대치를 구하지 못하도록 요구한다(hdu1520)
2: 나무 한 그루를 주고 각 노드에서 가장 먼 점의 거리를 구한다(hdu2196)
3:1>한 지도에 N개의 성이 있고, 각 성마다 일정한 보물이 있으며, 매 게임마다 M개의 성을 공략하여 안에 있는 보물을 획득할 수 있습니다.그러나 지리적 위치 때문에 일부 성곽은 직접 공략할 수 없기 때문에 이 성곽을 공략하려면 반드시 다른 특정한 성곽을 먼저 공략해야 한다.최대한 많은 보물을 구하려면 어느 M개의 성곽을 공략해야 합니다.(hdu1561)
문제풀이: 트리 dp+가방 2>각 노드에는 두 개의 값 버그와brain이 있습니다. 이 노드의 모든 버그를 청소할 때brain값을 받습니다. 부 노드가 비워질 때만 하위 노드를 청소할 수 있습니다. 청소는 일정한 인원이 필요합니다.M명, N개의 결점 트리를 정하고 최대 브레인과 (hdu1011)를 구한다.
3>현재 n개의 마을이 있습니다. m개의 마을을 매수하여 당신을 위해 투표를 하려고 합니다. 그 중에서 i번째 마을을 매수하는 대가는val[i]입니다.그러나 일부 마을은 종속관계가 있는데 B가 A국에 종속되면 A를 매수한 것도 B를 매수했다는 뜻이고 이런 관계는 전달된 것이다.-- 최소한 치러야 할 대가는 얼마인가.(poj3345)
4:1>나무 한 그루, 각 노드의 balance 값을 정의합니다. 이 노드를 제거한 숲의 모든 나무의 최대 노드 수입니다.최소 balance 값과 대응하는 노드 번호를 구합니다 (poj1655)
2>무방향 나무 T를 드립니다. 나무의 어떤 결점을 차례대로 제거하고, 그 결점을 제거한 후 숲 T'의 최대 지점을 구하세요.그리고 이 지점은 제거된 결점을 최대한 적게 요구한다.답이 여러 개 있을 수 있으므로 노드 번호에 따라 작은 출력(poj3107)
5:나무 한 그루에 n결점<=1000,K<=200을 주고 이 나무에서 크기가 k인 자수를 찾아 점권과 값을 최대로 한다(zoj3201)
6:나무그림에 점이 n개 있습니다.어느 점을 없애고 나머지 모든 연결자 그림의 점의 수량이 n/2를 초과하지 않도록 구하세요.이런 점이 많으면 오름차순으로 출력한다.n<=10000 (poj2378)
7:n개의 결점을 가진 뿌리 없는 나무에서 한 변을 삭제하여 남은 두 그루의 노드 값의 합을 절대값으로 최소화하고 얻은 최소 절대값(poj3140)을 구한다.
8: 약간의 점, 값, 약간의 변을 제시한 다음에 한 변을 제거한 후 연결된 두 부분으로 나누고 두 부분의 차이가 가장 적다(hdu2242)
9:n개의 점이 하나의 나무를 구성하고 최소한 몇 개의 변을 삭제해야 p개의 결점이 있는 자수 한 그루를 얻을 수 있는지 묻는다(poj1947)
10:나무 n<=1000(노드의 분지<=8), Snail은 뿌리에 있다. Snail은 어느 잎에 있는 house를 찾아야 한다. 그 중 일부 노드에worm이 있다. worm은 이 나무에서 Snail이 가장 빨리 house가 지나간 경로의 기대치를 찾을 수 있는지 알려준다(poj2057)
11:사과나무 하나 줄게요.N개의 노드가 있어요.노드마다 사과가 하나씩 있어요.즉 하나의 권한이 있어요.당신이 이 노드를 지나가면 이 권한을 얻을 수 있어요.반복해서 노드를 걷는 것은 한 번만 계산할 수 있어요.N-1개의 테두리를 줄게요.K걸음만 걸어서 얻을 수 있는 최대 권한과(poj2486)
12:두 갈래 사과나무에 사과가 맺히면 몇 그루의 가지를 잘라내고 Q개의 가지가 사과수까지 보존할 수 있도록 요구한다(ural1018)
13: 나무 한 그루를 정하고 최소한 몇 개의 변을 연결하여 각 점이 하나의 고리 안에 있도록 한다.(poj1848)
14: 나무 모양의 도시에 소방소를 세우지만 도시마다 최대 거리 제한이 있어 필요한 최소 비용을 구한다(poj2152)
위의 문제는 모두 푸는 것이 좋겠다.