CF633F·The Chocolate Spree

CF633F·The Chocolate Spree"/>

CF633F·The Chocolate Spree

初见安~这里是传送门：Codeforces 633 F

Alice and Bob have a tree (undirected acyclic connected graph). There are ai chocolates waiting to be picked up in the i-th vertex of the tree. First, they choose two different vertices as their starting positions (Alice chooses first) and take all the chocolates contained in them.

Then, they alternate their moves, selecting one vertex at a time and collecting all chocolates from this node. To make things more interesting, they decided that one can select a vertex only if he/she selected a vertex adjacent to that one at his/her previous turn and this vertex has not been already chosen by any of them during other move.

If at any moment one of them is not able to select the node that satisfy all the rules, he/she will skip his turns and let the other person pick chocolates as long as he/she can. This goes on until both of them cannot pick chocolates any further.

Due to their greed for chocolates, they want to collect as many chocolates as possible. However, as they are friends they only care about the total number of chocolates they obtain together. What is the maximum total number of chocolates they may pick?

Input

The first line of the input contains the single integer n (2 ≤ n ≤ 100 000) — the number of vertices in the tree.

The second line contains n integers ai (1 ≤ ai ≤ 109), i-th of these numbers stands for the number of chocolates stored at the node i.

Then follow n - 1 lines that describe the tree. Each of them contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of vertices connected by the i-th edge.

Output

Print the number of chocolates Alice and Bob can collect together if they behave optimally.

Examples

input

9
1 2 3 4 5 6 7 8 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9

output

25

 input

2
20 10
1 2

output

30

Note

In the first sample, Alice may start at the vertex 9 and Bob at vertex 8. Alice will select vertex 1 and Bob has no options now. Alice selects the vertex 7 and they both stop.

In the second sample, both of them will pick either of the nodes alternately.

Sol

本狸第一次做的时候天真地直接树形dp算出了直径的长度+另一条路径的长度，然后WA了90分……QuQ还是太天真了。

题意转化过来就是——给你一棵树，求两条路径使其点权和最大并且不相交。

很明显的是，如果只求一条路径要求点权和最大，我们就求直径即可。现在要再加一条，有可能是在直径以外，有可能是让直径退几步往外拐。也就是说只有以下两种情况：【图中的长链是直径】

1.各占一部分直径，并往直径以外的链延伸一部分

2.一条为直径，一条为直径以外的子树的直径：

这两种情况划分出来就很好处理了——我们首先要处理出直径并取出直径上的点，再依次计算从该点往非直径的点延伸的最长链的长度，处理出从左往右取第一条链的最优值，从右往左取第二条链的最优值，左右匹配即可。对于第二种情况，我们直接用直径的长度加上计算第一种情况时处理出来的最长链的长度的最大匹配结果即可。

看看代码会比较直观——

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define maxn 100005
#define int long long
using namespace std;
typedef long long ll;
int read() {int x = 0, f = 1, ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();return x * f;
}struct edge {int to, nxt;} e[maxn << 1];
int head[maxn], k = 0;
void add(int u, int v) {e[k] = {v, head[u]}; head[u] = k++;}int n, val[maxn], root = 0, fa[maxn];
ll dis[maxn];
void dfs(int u) {dis[u] += val[u];//计算dis用于找直径 for(int i = head[u]; ~i; i = e[i].nxt) {register int v = e[i].to; if(v == fa[u]) continue;dis[v] += dis[u]; fa[v] = u; dfs(v);}if(dis[u] > dis[root]) root = u;
}ll f[maxn], ans = 0;
bool vis[maxn];
void check(int u) {f[u] = val[u];for(int i = head[u]; ~i; i = e[i].nxt) {register int v = e[i].to; if(v == fa[u] || vis[v]) continue;fa[v] = u; check(v); if(!vis[u]) ans = max(ans, f[u] + f[v]);//一定要不是直径上的的点才能这样匹配第二种情况 f[u] = max(f[u], f[v] + val[u]); //找最长链 }if(!vis[u]) ans = max(ans, f[u]);//也可以是直链。 
}ll pre[maxn], suf[maxn], q[maxn], tot = 0;
signed main() {memset(head, -1, sizeof head);n = read();for(int i = 1; i <= n; i++) val[i] = read();for(int u, v, i = 1; i < n; i++) u = read(), v = read(), add(u, v), add(v, u);dfs(1);//找直径的一端 fa[root] = 0; memset(dis, 0, sizeof dis);dfs(root);//找直径的另一端 ，这里旋转了一下树的形态所以前一端就是根 register int ls = root;while(ls) q[++tot] = ls, vis[ls] = true, ls = fa[ls];//取出直径 ，打标记 ls = root;while(ls) check(ls), ls = fa[ls];//挨个处理直径上的点的最长链 ll sum = 0;for(int i = 1; i <= tot; i++) pre[i] = max(pre[i - 1], sum + f[q[i]]), sum += val[q[i]];//从前往后 ans += sum; sum = 0;//现在的ans是第二种情况的答案 for(int i = tot; i > 0; i--) suf[i] = max(suf[i + 1], sum + f[q[i]]), sum += val[q[i]];//从后往前 for(int i = 1; i < tot; i++) ans = max(ans, pre[i] + suf[i + 1]);//匹配 第一种情况 printf("%lld\n", ans);return 0;
}
/*
10
99 60 74 69 4 7 36 64 89 76
1 2
2 3
1 4
2 5
3 6
3 7
5 8
4 9
9 10
out:578
*/

迎评：）

——End——