프로그래밍언어문법/실전문제풀어보기

트리관련 문제

파아란기쁨1 2021. 5. 20. 15:56
반응형

중급] 1949 : 우수마을 https://www.acmicpc.net/problem/1949 

더보기 
#include <iostream>
#include <vector>

using namespace std;

struct data{
    int selectCnt;
    int nonSelectCnt;
};

int num[100010];
int visited[100010];
vector <int> link[100010];
int n;

struct data dfs(int next)
{
    struct data res;
    res.nonSelectCnt = 0;
    res.selectCnt = 0;
    if(visited[next]) return res;
    visited[next] = 1;
    int nextSelectCnt = 0;
    int nextNonSelectCnt = 0;
    struct data imsi;
    for(int i = 0;i<link[next].size();i++)
    {
        imsi = dfs(link[next][i]);
        res.nonSelectCnt += max(imsi.selectCnt,imsi.nonSelectCnt);
        res.selectCnt += imsi.nonSelectCnt;
    }
    res.selectCnt += num[next];
    return res;
};

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;
    for(int i=1;i<=n;i++) cin >> num[i];
    int a,b;
    for(int i=0;i<n-1;i++)
    {
        cin >> a >> b;

        link[a].push_back(b);
        link[b].push_back(a);
    }
    struct data res;
    res = dfs(1);

    cout << max(res.nonSelectCnt,res.selectCnt);
    return 0;
}

 

중급] 2161 : 트리순회 - http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1422&sca=99&page=12 

중급] 1029 : 모빌 - http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=308&sca=6020 

 

 

반응형