Description
有一棵树，每个点有一个权值，找到一个权值最大的"乙烷"模型。
"乙烷"模型是指：
其中黑点表示可以有0个或多个点。
Sample Input
8
1 1 1 1 1 1 1 1 //点权
1 2 //建树
1 3
1 4
1 5
2 6
2 7
2 8
Sample Output
8
看到这道题有点蒙，想了一会儿想出是树形DP了，就是不会写，就想着打个暴力，还没打对。。。（我吐了）
这道题正解就是树形DP，我们考虑它的状态是什么。
（我们cjh学长的画功真是太厉害了！）
0代表一个点，1代表一条链，2代表两条链...
那转移呢？
(x)代表父亲节点，(to)代表(x)的一个儿子。
我们是从叶子节点向根节点转移的，所以当(x)状态为0，(to)状态为1时，它是无法转移到一个合法的状态的（可以手画画）。
#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
const int N = 1e5 + 5, inf = 1e9;
int n;
long long ans;
int a[N];
long long f[N][8];
vector <int> son[N];
void init() {
n = read();
for(int i = 1;i <= n; i++) a[i] = read();
for(int i = 1, x, y;i <= n - 1; i++) {
x = read(); y = read();
son[x].push_back(y);
son[y].push_back(x);
}
memset(f, 0xf3, sizeof(f));
}
void dfs(int x, int fa) {
f[x][0] = a[x];
long long tmp[8];
for(int i = 0;i < (int)son[x].size(); i++) {
int y = son[x][i]; if(y == fa) continue;
// cout << x << " " << y << endl;
dfs(y, x);
long long *u = f[x], *v = f[y];
for(int j = 0;j < 8; j++) tmp[j] = u[j];
tmp[1] = max(tmp[1], u[0] + max(v[0], v[1]));
tmp[2] = max(tmp[2], u[1] + max(v[0], v[1]));
tmp[3] = max(tmp[3], u[2] + max(v[0], v[1]));
tmp[4] = max(tmp[4], u[0] + max(v[3], v[4]));
tmp[5] = max(tmp[5], u[4] + max(v[0], v[1]));
tmp[5] = max(tmp[5], u[1] + max(v[3], v[4]));
tmp[6] = max(tmp[6], u[5] + max(v[0], v[1]));
tmp[6] = max(tmp[6], u[2] + max(v[3], v[4]));
tmp[7] = max(tmp[7], u[0] + max(v[6], v[7]));
// for(int j = 0;j < 8; j++) cout << tmp[j] << " ";
// cout << endl;
ans = max(ans, tmp[7]);
ans = max(ans, max(u[3], u[4]) + max(v[3], v[4]));
ans = max(ans, max(u[6], u[7]) + max(v[0], v[1]));
// cout << ans << endl;
for(int j = 0;j < 8; j++) u[j] = tmp[j];
}
}
void work() {
ans = -inf;
dfs(1, 0);
printf("%lld", ans);
}
int main() {
freopen("misaka.in","r",stdin); freopen("misaka.out","w",stdout);
init();
work();
fclose(stdin); fclose(stdout);
return 0;
}
（貌似这题是有点恶心哈）