思路:
经典树形dp
dp[i][0]表示i的子树中以i为端点的最大链
dp[i][1]表是整棵树中除去i的子树剩下的部分以i为端点的最大链
最后答案就是以i为端点的最大链和次大链拼起来(除了一些特殊情况,比如一条链更大,或者只有一条链)
代码:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pi acos(-1.0)
#define LL long long
//#define mp make_pair
#define pb push_back
#define ls rt<<1, l, m
#define rs rt<<1|1, m+1, r
#define ULL unsigned LL
#define pll pair<LL, LL>
#define pli pair<LL, int>
#define pii pair<int, int>
#define piii pair<pii, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
//head const int N = 1e5 + ;
vector<int> g[N];
int a[N], ans[N];
int dp[N][];
void dfs1(int u, int o) {
dp[u][] = a[u];
for (int v : g[u]) {
if(v != o) {
dfs1(v, u);
dp[u][] = max(dp[u][], a[u] + dp[v][]);
}
}
}
void dfs2(int u, int o) {
if(u == ) dp[u][] = a[u];
int v1, mx1 = INT_MIN, v2, mx2 = INT_MIN;
for (int v : g[u]) {
if(v != o) {
int tmp = dp[v][] + a[u];
if(tmp > mx1) {
mx2 = mx1;
v2 = v1;
mx1 = tmp;
v1 = v;
}
else if(tmp == mx1 || tmp > mx2) {
mx2 = tmp;
v2 = v;
}
}
}
if(dp[u][] > mx1) {
mx2 = mx1;
v2 = v1;
mx1 = dp[u][];
v1 = -;
}
else if(dp[u][] == mx1 || dp[u][] > mx2){
mx2 = dp[u][];
v2 = -;
}
ans[u] = a[u];
if(mx1 != INT_MIN && mx2 != INT_MIN) ans[u] = max(ans[u], mx1 + mx2 - a[u]);
else if(mx1 != INT_MIN) ans[u] = max(ans[u], mx1);
else ans[u] = max(ans[u], mx2);
ans[u] = max(ans[u], mx1);
ans[u] = max(ans[u], mx2);
for (int v : g[u]) {
if(v != o) {
dp[v][] = a[v];
if(v == v1) {
dp[v][] = max(dp[v][], mx2 + a[v]);
}
else {
dp[v][] = max(dp[v][], mx1 + a[v]);
}
dfs2(v, u);
}
} }
int main() {
int n, m, u, v, q;
scanf("%d %d", &n, &m);
for (int i = ; i <= n; i++) scanf("%d", &a[i]);
for (int i = ; i < n; i++) {
scanf("%d %d", &u, &v);
g[u].pb(v);
g[v].pb(u);
}
dfs1(, );
dfs2(, );
while(m--) {
scanf("%d", &q);
printf("%d\n", ans[q]);
}
return ;
}