상세 트 리 DP

머리말
N 개의 노드 가 있 는 트 리 를 지정 합 니 다.(일반적으로 뿌리 가 없 는 트 리 이면 N-1 개의 방향 이 없 음)노드 를 루트 노드 로 선택 할 수 있 습 니 다.
일반적으로 노드 가 깊이 에서 얕 은(서브 트 리 가 작은 것 에서 큰 것 까지)순서 로 dp 단계 순서 로 한다.
dp 의 상태 표시 에서 첫 번 째 는 노드 번호(노드 번 호 는 이 노드 를 뿌리 로 하 는 서브 트 리 를 대표 합 니 다)
각 노드 x 에 대해 먼저 그의 모든 하위 노드 에 걸 쳐 dp 를 하고 거 슬러 올 라 갈 때 하위 노드 에서 x 로 상태 이동 을 한다.
A - Anniversary part
N 명의 직원,번 호 는 1~N 입 니 다.
그들 사이 에는 종속 관계 가 있다.즉,그들의 관 계 는 마치 교장 을 뿌리 로 하 는 나무 와 같 고,아버지의 결점 은 바로 자식 결점 의 직속 상사 이다.지금 연회 가 있 습 니 다.연회 에 직원 을 초대 할 때마다 i 는 일정한 즐거움 지 수 를 증가 시 킵 니 다.그러나 어떤 직원 의 직속 상사 가 오 면 이 직원 은 오지 않 습 니 다.어떤 직원 을 초대 하면 즐거움 지수 가 가장 크 고 수출 이 가장 큰 즐거움 지 수 를 계산 할 수 있 습 니까?
dp[x][0]을 설정 하면 x 를 뿌리 로 하 는 서브 트 리 에서 일부 직원 을 초대 하고 x 가 참가 하지 않 을 때 즐거움 지수 총계 의 최대 치 를 나타 낸다.이때 x 서브 노드(직접 부하)는 참가 할 수도 있 고 참가 하지 않 을 수도 있다(s 는 x 서브 노드 를 나타 낸다).

dp[x][1]을 설정 하면 x 를 뿌리 로 하 는 서브 트 리 에서 일부 직원 을 초대 하고 x 가 참가 할 때 쾌락 지수 총계 의 최대 치 를 나타 낸다.이때 x 서브 노드(직접 부하)는 참가 할 수 없다.H[x]는 현재 노드(x)의 쾌락 지수(s 는 x 서브 노드 를 나타 낸다)를 나타 낸다.

이 문 제 는 뿌리 가 있 는 나 무 를 주면 뿌리 노드 부터 시작 할 수 있 습 니 다.dp 목 표 는 max(F[root,0],F[root,1])시간 복잡 도 ON 입 니 다.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> son[10010];
int dp[10010][2];//0   ，1  
int v[10010];//        
int h[10010];//      
int n;

void DFS(int x){
    dp[x][0] = 0;
    dp[x][1] = h[x];
    for (int i = 0; i < son[x].size(); i++)
    {
        int y = son[x][i];
        DP(y);
        dp[x][0] += max(dp[y][0],dp[y][1]);
        dp[x][1] += dp[y][0];
    }
}

int main(){
    cin>>n;
    for (int i = 1; i <=n ; i++)
        scanf("%d",&h[i]);
    for (int i = 1; i <n ; i++)
    {
        int x,y;
        cin>>x>>y;
        v[x] = 1;//x   
        son[y].push_back(x);//x y    
    }
    int root;
    for (int i = 1; i <= n; i++)
        if(!v[i]){ //i    
            root = i;
            break;
        }
    DFS(root);
    cout << max(dp[root][0],dp[root][1]) << endl;
    return 0;
}

B - Strategic game
n 개의 점 이 있 습 니 다.어떤 점 에 보초병 을 배치 하고 모든 보초병 은 그것 과 연 결 된 점 을 감시 할 수 있 습 니 다.모든 점 을 감시 하 는 데 필요 한 최소 보초병 수 를 물 어 볼 수 있 습 니 다.
즉,n 개의 결점 이 있 는 나 무 는 그 중의 정점 을 선택 하여 트 리 의 모든 변(u,v),u 와 v 가 적어도 하 나 를 선택 할 수 있 도록 해 야 한다.선택 한 정점 이 가장 적은 방안 을 제시 해 야 한다.
dp[x][0]을 설정 하면 노드 x 를 선택 하지 않 은 상태 에서 x 를 뿌리 노드 로 하 는 서브 트 리 로 최소 선택 할 노드 수 를 표시 합 니 다.
i 가 잎 노드 일 때

i 가 잎 노드 가 아 닐 때(s 는 x 자 노드 를 표시 합 니 다)

dp[x][1]을 설정 하면 노드 x 를 선택 한 상황 에서 x 를 루트 노드 로 하 는 서브 트 리 로 최소 선택 할 노드 수 를 표시 합 니 다.
i 가 잎 노드 일 때

i 가 잎 노드 가 아 닐 때(s 는 x 자 노드 를 표시 합 니 다)

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define maxn 1508
using namespace std;

int dp[maxn][2];
int soncnt[maxn];
int parent[maxn];
int n;

void DFS(int x) {
    int i, d1=0, d0=0;
    if (soncnt[x] == 0) {
        dp[x][0] = 0;
        dp[x][1] = 1;
        return;
    }
    for (i=0; i < n; i++) {
        if (parent[i] == x) {
            DFS(i);
            d1 += min(dp[i][0], dp[i][1]);
            d0 += dp[i][1];
        }
    }
    dp[x][1] = d1 + 1;
    dp[x][0] = d0;
}

int main() {
    int dad, son, m;
    while (cin >> n) {
        memset(soncnt, 0, sizeof(soncnt));
        memset(parent, -1, sizeof(parent));
        int root = -1;
        for (int i = 0; i < n; i++) {
            scanf("%d:(%d)", &dad, &m);
            soncnt[dad] = m;
            if (root == -1) {
                root = dad;
            }
            while (m--) {
                scanf("%d", &son);
                parent[son] = dad;
            }
        }
        DFS(root);
        cout << min(dp[root][0], dp[root][1]) << endl;
    }
    return 0;
}

C - Tree Cutting
n 개의 결점 을 가 진 나 무 를 주 고 노드 번 호 는 1~n 이다.
―어떤 결점 을 삭제 한 후 나머지 키 트 리 의 크기 는 원 총 점 의 절반 보다 작 습 니까?
한 노드 를 철거 한 후에 나머지 부분 은 몇 명의 아들 의 나무 와 이 노드 상층 부 에 연 결 된 나머지 부분(n-size[i])이다.이런 연결 블록 의 크기 가 n/2 를 초과 하지 않 으 면 이 노드 는 조건 을 만족 시 킬 수 있다.따라서 우 리 는 먼저 각 노드 가 관할 하 는 그 나무의 크기 를 구하 고 아래 에서 위로 모든 노드 에 그 나무 규모(이 점 규모=그 아들 의 규모 와+1)를 구 할 수 있다.
나 무 를 만 들 때 직접 연결 표(vector)로 무 방향 변 을 저장 할 수 있 습 니 다.이 때 각 점 과 연 결 된 것 이 아버지 노드 인지 자식 노드 인지 구분 할 수 없 기 때문에 문 제 를 일 으 킬 수 있 습 니 다.dfs 때 아버지 노드 를 아들 노드 로 오인 하고 해결 방법 은 재 귀 할 때 아버지 노드 번호 에 들 어간 다음 에 재 귀 하고 규 모 를 계산 하 는 것 입 니 다.크기 를 비교 할 때 는 피해 주시 면 됩 니 다.

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n;
int root;
vector<int>G[10000+400];
vector<int>ans;
int sz[10000+400];
 
void dfs(int par,int u){
    sz[u]=1;
    for(int i=0;i<(int)G[u].size();i++){
        if(G[u][i]!=par)
            dfs(u,G[u][i]);
    }
    int piece=0;
    for(int i=0;i<(int)G[u].size();i++)
        if(par!=G[u][i]){
            sz[u]+=sz[G[u][i]];
            piece=max(piece,sz[G[u][i]]);
        }
    piece=max(piece,n-sz[u]);
    if(piece<=n/2)
        ans.push_back(u);
}
 
int main(){
    while(cin>>n){
        memset(sz,0,sizeof(sz));
        int x,y;
        for(int i=0;i<n-1;i++){
            scanf("%d%d",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(0,1);
        sort(ans.begin(),ans.end());
        for(int i=0;i<(int)ans.size();i++)
            cout<<ans[i]<<endl;
    }
    return 0;
}

LCA 최근 공공 조상
배가(2 점 에 기초 한 방법)
만약 에 나무의 두 점 이 같은 깊이 에 있 을 때 위로 mid 걸음 을 뛰 는 것 은 단조 로 운 것 이 분명 하 다.
만약 그들 이 위로 뛰 어 오 르 는 mid 걸음 이 같은 점 이 라면,이 점 은 그들의 공동 조상 이지 만,반드시 최근 의 공공 조상 은 아니다.
그러면 만약 에 우리 가 모든 점 에서 위로 몇 걸음 뛰 는 것 이 누구 인지 빨리 얻 을 수 있다 면 분명히 우 리 는 2 점 을 이용 하여 LCA 를 구 할 수 있다.
이것 은 배로 늘 려 서 할 수 있다.
배가 되 는 사상 은 사실 매우 간단 하 다.바로 이 진 사상 을 이용 하 는 것 이다.명확 한 결론 은 다음 과 같다.
노드 u 위로 뛰 기 2^(k+1)천의 조상=(노드 u 위로 뛰 기 2k 천의 조상)위로 뛰 기 2k 천의 조상
코드 로 표시 하면:

fa[u][k + 1] = fa[ fa[u][k] ][k];

이것 의 예비 처리 도 매우 간단 하 다.우 리 는 모든 fa[u][0]을 초기 화하 면 된다.왜냐하면 다음 부분 은 위의 공식 에 따라 전달 할 수 있 기 때문이다.
그리고 이것 을 미리 처리 한 후에 우 리 는 이것 에 따라 2 분 을 진행 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다.

int fa[maxn][20], dep[maxn];

void dfs(int u, int f, int d)
{
    dep[u] = d;
    fa[u][0] = f;
    for(int i = 1; i < 20; ++i)
    {
        fa[u][i] = fa[fa[u][i -  1]][i] - 1;
    }
    for(int i = head[u]; ~i; i = nxt[i])
    {
        int t = to[i];
        if(t != f)
        {
            dfs(t, u, d + 1);
        }
    }
}

int lca(int u, int v)
{
    if(dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for(int i = 0; i < k; ++i)
    {
        if((1 << i) & k) u = fa[u][i];
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; --i)
    {
        if(fa[u][i] != fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

이상 은 트 리 DP 에 대한 상세 한 내용 입 니 다.트 리 DP 에 관 한 자 료 는 저희 의 다른 관련 글 을 주목 해 주 십시오!