一份简单的美术作业（Art）
题意：
给你一棵树，树上 \(n\) 个节点和 \(n-1\) 条边，每个点有一个权值，每两个黑点之间必须间隔至少一个白点，求黑点权值总和最大值，并且输出任意一种达成最大值的取点合法方案。
sol：
对于第一问，采用树形 dp。定义 \(f_{i,0/1}\) 为当前节点为 \(i\)，当前点取或不取能其子树种达到的点权最大值，定义其子节点为 \(u\) 则有：
-
当前节点不取，下面一个节点可以有取或不取两种选择，即 \(f_{i,0}=\sum\max\{f_{u,1},f_{u,0}\}\)。
-
当前节点要取，下面一个节点不能取，即 \(f_{i,1}=w_i+\sum f_{u,0}\)。
最后答案就为 \(\max\{f_{root,0},f_{root,1}\}\)。
可以拿到 \(30\%\) 的分数。
第二问，可以在 dp 过程中加入一个 vector 数组 \(e\)，对于每个子节点，如果取其结果最优，则在 \(e\) 中压入 \(1\)，否则压入 \(0\)。
然后再进行一遍 dfs，如果这个节点在 \(e\) 中标号为 \(1\)，说明这样决策最优，则它的子节点全部不能取，可以在递归的时候加入标记，如果标记为 \(0\) 则表示全部不取，把取到的数压入另一个 vector 数组 \(ans\) 中。
最后点的个数就是 ans.size()，方案就直接遍历 \(ans\) 数组输出。
复杂度 \(O(n\log n)\)，\(\log\) 取在 vector 上。
最后，十年 OI 一场空，不开 long long 见祖宗。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define SIZE 100005
using namespace std;
int n, ver[2*SIZE], nxt[2*SIZE], head[SIZE], tot, cnt;
long long f[SIZE][2];
//f[i][0/1]表示当前处在第 i 个节点，当前节点染黑或不染黑，存储这个点的子树内染黑点权总和最大值
long long w[2*SIZE];
vector<int> e[SIZE], ans;
void add(int x, int y){
ver[++tot]=y, nxt[tot]=head[x], head[x]=tot;
}
void dfs(int x, int fa){
f[x][1]=w[x];
for (int i=head[x]; i; i=nxt[i]){
int y=ver[i];
if(y!=fa){
dfs(y, x);
f[x][1]+=f[y][0];
f[x][0]+=max(f[y][1], f[y][0]);
if(f[y][1]>f[y][0]) e[x].push_back(1);
else e[x].push_back(0);
}
}
return;
}
void dfs1(int x, int fa, bool flag){
if(flag) ans.push_back(x);
int cnt=0;
for (int i=head[x]; i; i=nxt[i]){
int y=ver[i];
if(y!=fa){
if(flag) dfs1(y, x, 0);
else dfs1(y, x, e[x][cnt++]);
}
}
}
int main(){
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%lld", &w[i]);
for (int i=1; i<n; i++){
int u, v;;
scanf("%d%d", &u, &v);
add(u, v);add(v, u);
}
dfs(1, 0);
printf("%lld\n", max(f[1][1], f[1][0]));
if(f[1][1]>f[1][0]) dfs1(1, 0, 1);
else dfs1(1, 0, 0);
printf("%lld ", ans.size());
for (int i=0; i<ans.size(); i++) printf("%d ", ans[i]);
return 0;
}