2213

값을 구한 후 그 값이 어떻게 나왔는지 추적을 해야 하는 문제

 

사회망서비스(SNS)문제와 매우 비슷하다.

 

---

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
int dp[10010][2];
vector<int> v[10010];
int W[10010];
vector<int> ansset;

void dfs(int x,int par){
    if(dp[x][0] != -1) return;
     dp[x][0] = 0;
     dp[x][1] = W[x]; 
	for(int i:v[x]){
	if(i==par) continue;
	    dfs(i,x);
		dp[x][1] += dp[i][0]; 
		dp[x][0] += max(dp[i][1],dp[i][0]);  
}
   return ;
}
void sol(int x,int par,bool flag){
	if(flag) ansset.push_back(x);
	for(int i: v[x]){
		if(i == par) continue;
		if(!flag) sol(i,x,dp[i][0] <dp[i][1]);
		else sol(i,x,0);

	}
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	for(int i = 1; i <= N ;i++ )cin>>W[i];
	for(int i=0,u,x;i<N -1;i++){
		cin>>u>>x;
		v[u].push_back(x);
		v[x].push_back(u);
	}
	memset(dp,-1,sizeof(dp));
	v[0].push_back(1);
	dfs(1,0);
	int sz = max(dp[1][0],dp[1][1]);
	cout<<sz<<'\n';
	sol(1,0,sz == dp[1][0] ? 0 : 1);
	sort(ansset.begin(),ansset.end());
	for(int i: ansset) cout<<i<<" "; 
	return 0;
}