金色1-100準1949優秀村

優秀な村

https://www.acmicpc.net/problem/1949

方法

答えを求めるためには、隣接しない村を選んで最大値を求めるべきだ.村が一列なら簡単にDPを使って村を選ぶことができますが、村は木の構造なので考慮すべき部分があります.
一つの村が複数の村につながっているとき、DPをどう扱うかを考え、現在の村を選ぶときと選択していない村を選ぶときを分けて考える.
現在の村を選択した場合、現在の村に隣接する村は選択不可能であり、隣接する村ごとに選択がない場合に発生する可能性のある最大値を加えて結果を保存し、逆に現在の村を選択していない場合の結果も算出して結果を保存する.
このように逐次漸進的なリフノードから最大値を上に増やし,ルートノードになると村全体の最大値を求めることができる.

に答える

リフノードに遡るために回帰を利用した.再帰関数dfs内の繰返し文では,接続されたノードにアクセスして最大値を求め,2つのケースに分けてそれぞれ保存とする.
現在のノードが選択されている場合、隣接するノードは絶対に選択できないので、考慮する必要はありません.non select sumを追加するだけです.
逆に、現在のノードが選択されていない場合、隣接するノードを選択するか、選択しない場合があるため、相互比較値が大きくなる場合があります.
すべての隣接ノードについて最大値を計算すると、選択が保存され、2つの最大値が選択されていない選択クラスが返されます.
メイン関数では、dfs関数から返されるselectionクラスの変数値を比較することで、大きな値を出力できます.

コード#コード#

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int value[10001];
bool visited[10001];
vector<vector<int>> link;

class selection
{
public:
	int select_sum;
	int non_select_sum;

	selection(int ss, int nss)
	{
		this->select_sum = ss;
		this->non_select_sum = nss;
	}
};

selection dfs(int n)
{
	int sum = value[n];
	int non_sum = 0;

	for (int i = 0; i < link[n].size(); i++)
	{
		if (visited[link[n][i]])
			continue;

		visited[link[n][i]] = true;
		selection sel = dfs(link[n][i]);

		// 현재 노드 선택
		sum += sel.non_select_sum;

		// 현재 노드 미선택
		if (sel.non_select_sum > sel.select_sum)
			non_sum += sel.non_select_sum;
		else
			non_sum += sel.select_sum;
	}
	
	selection result = selection(sum, non_sum);
	return result;
}

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

	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		vector<int> temp;
		link.push_back(temp);
		cin >> value[i];
		if (i == N)
			link.push_back(temp);
	}

	for (int i = 0; i < N - 1; i++)
	{
		int a, b;
		cin >> a >> b;
		link[a].push_back(b);
		link[b].push_back(a);
	}

	visited[1] = true;
	selection answer = dfs(1);

	cout << max(answer.select_sum, answer.non_select_sum) << endl;

	return 0;
}