poj 2342 【Anniversary party】树形dp

题目传送门//res tp poj

题意

给出一棵有权树，求一个节点集的权值和，满足集合内的任意两点不存在边

分析

每个点有选中与不选中两种状态，对于第\(i\)个点，记选中为\(sel_i\)，不选中为\(insel_i\)

若某一节点选中，则其子节点都不能选中。

若某一节点不选中，则其子节点有两种选择：1.选中 2.不选中

故

\[sel_i = val_i +\sum_j insel_j
\]

\[insel_i = \sum_j max\{insel_j,sel_j\}
\]

其中\(j\) 是\(i\)的子节点，\(val_i\)是节点\(i\)的权值

设\(rt\)为该树的根

则答案为

\[ans = max\{sel_{rt},insel_{rt}\}
\]

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<deque>

#define rep(i,a,b) for(int i=(a);i<=(b);++i)

#define per(i,a,b) for(int i = (a);i>=(b);--i)

#define fo(i,a,b) for(int i =(a);i<(b);++i)

#define de(x) cout<<#x<<" = "<<x<<endl;

#define endl '\n'

#define ls(p) ((p)<<1)

#define rs(p) (((p)<<1)|1)

using namespace std;

typedef long long ll;

const int mn = 6e3 + 10;

int n;

int u[mn],inu[mn];

int val[mn];

struct E{

	int firs,lasts;

	int fa;

	int nextbro;

}e[mn];

void dfs(int r){

	int tpos = e[r].firs;

	while(tpos){

		dfs(tpos);

		tpos = e[tpos].nextbro;

	}

	tpos = e[r].firs;

	u[r] += val[r];

	while(tpos){

		u[r] += inu[tpos];

		inu[r] += max(inu[tpos],u[tpos]);

		tpos = e[tpos].nextbro;

	}

}

int main(){

	scanf("%d",&n);

	rep(i,1,n)scanf("%d",&val[i]);

	int tf,ts;

	rep(i,1,n){

		scanf("%d %d",&ts,&tf);

		if(e[tf].firs){

			e[e[tf].lasts].nextbro = ts;

			e[tf].lasts = ts;

		}

		else{

			e[tf].firs = e[tf].lasts = ts;

		}

		e[ts].fa = tf;

	}

	int root = 1;

	while(e[root].fa) root = e[root].fa;

	//de(root)

	dfs(root);

	printf("%d\n",max(u[root], inu[root]));

}

巴特西

poj 2342 【Anniversary party】树形dp

题意

分析

最新文章

热门文章