【樹形DP】(2015)第6回ブルーブリッジカップ省試合C/C++B組問題解(第10題)

第十題
タイトル
生命の木はXの森の中で、神は生命の木を作りました.彼は各木の各ノード(葉は1つのノードとも呼ばれる)に、この点の調和値を表す整数をマークした.神はこの木の中で1つの非空のノードセットSを選んで、Sの中の任意の2つの点a,bに対して1つの点列{a,v 1,v 2,...,vk,b}が存在して、この点列の中の各点がSの中の要素で、シーケンスの中の隣接する2つの点の間に1本の辺がつながっているようにします.この前提の下で、神はSの中の点の対応する整数の和をできるだけ大きくします.この最大の和は神が生命の木に与えた採点である.atmの努力を経て、彼は神が木の上のすべてのノードに与えた整数を知っていた.しかしatmは計算が苦手なので、どのように効果的に採点するか分からない.彼はあなたが彼のために木の点数を計算するプログラムを書く必要があります.「入力フォーマット」の最初の行の整数nは、このツリーにn個のノードがあることを示します.2行目のn個の整数は、各ノードのスコアを順次表す.次にn−1行、各行2個の整数u,vは、uからvまでのエッジが存在することを示す.これは木なので、環は存在しません.「出力フォーマット」は、神がこの木に与えた点数を表す1行1つの数を出力します.「サンプル入力」51-2-34 54 23 11 22 5「サンプル出力」8「データ範囲」30%のデータ、n<=10 100%のデータ、0構想分析
     
この問題のタイプは、DFSでリーフノードを選択して下から上へ演算を開始するツリーダイナミックプランニングです.通常の考え方でツリーのルートから下へ再帰すれば、2つのサブノードが選択されているかどうかを判断するためです.逆に、葉のノードから始めると、2つの点を判断する必要はなく、父親のノードが選択されているか選択されていないかを直接判断する必要はありません.値を最大にするには、リーフノードから開始すると効率が向上します.   
各ノードについては2つの可能性しかない、すなわち選択するか選択しないので、dp[N][2]のような2次元配列が確立される.ここでNはノード数を表し、後の2はノードごとに2つの選択を表すので、dp[i][0]はi番目のノードが選択しない場合の重み値を表し、dp[i][1]はi番目のノードが選択された場合の重み値を表し、逆プッシュを開始することができる.dfs(int u,int v)は、それぞれ、開始ノードuとある親ノードf,fノードのときにDFSを終了させるフラグビットノードを表す.
類似問題->クリックしてリンクを開く
実行結果8
ACコード

#include 
#include
#include
#include
using namespace std;
const int nmax=100001;
vectorG[nmax];//    
int dp[nmax][2];//dp[i]   i               （     ，      i  ）
//         ，     
int val[nmax];
int dfs(int u,int v){
	for(int i=0;i>n;
	
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++){//         
		cin>>value;
		val[i]=value;
		dp[i][1]=val[i];
	}
	for(int i=1;i>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,-1);
	int ans=max(dp[1][0],dp[1][1]);
	printf("%d
",ans);  
	//cout<