BZOJ什么垃圾机器….DBZOJ都能A，BZOJ T飞
上来直接点分就行了，用动态开点线段树维护已经出现过的最小值为x的最长的路径。
然后合并的时候，拿一个路径去和最小值大于等于他的更新答案即可。
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
typedef long long int int_t;
using std::cin;
using std::cout;
using std::endl;
const int_t INF = 0x7fffffff;
const int_t LARGE = 1e5;
const int_t RANGE = 65536;
struct Data {
int depth;
int val;
Data(int depth = -1, int val = 1) {
this->depth = depth;
this->val = val;
}
};
std::ostream& operator<<(std::ostream& os, const Data& data) {
os << "Data{depth=" << data.depth << ",val=" << data.val << "}";
return os;
}
void* allocate();
struct Node {
int begin;
int end;
int value;
Node *left, *right;
Node(int begin, int end) {
this->begin = begin;
this->end = end;
value = -INF;
left = right = NULL;
}
void maintain() {
value = -INF;
if (left) value = std::max(value, left->value);
if (right) value = std::max(value, right->value);
}
int query(int begin, int end) {
if (end < this->begin || begin > this->end) return -INF;
if (this->begin >= begin && this->end <= end) return this->value;
int result = -INF;
if (left) result = std::max(result, left->query(begin, end));
if (right) result = std::max(result, right->query(begin, end));
return result;
}
void maxTo(int pos, int val) {
if (begin == end) {
this->value = std::max(value, val);
return;
}
int mid = (begin + end) / 2;
if (pos <= mid) {
if (left == NULL) left = new (allocate()) Node(begin, mid);
left->maxTo(pos, val);
} else {
if (right == NULL) right = new (allocate()) Node(mid + 1, end);
right->maxTo(pos, val);
}
maintain();
}
};
int used = 0;
void* allocate() {
static char buf[LARGE * 20 * sizeof(Node)];
return buf + (used++) * sizeof(Node);
}
int vals[LARGE + 1];
bool removed[LARGE + 1];
int size[LARGE + 1];
std::vector<int> graph[LARGE + 1];
int n;
//统计子树大小和路径长度及权值
void DFS1(int vtx, int from, int depth, std::vector<Data>& vec,
int minval = INF, bool save = false) {
minval = std::min(minval, vals[vtx]);
if (save) vec.push_back(Data(depth, minval));
size[vtx] = 1;
for (int i = 0; i < graph[vtx].size(); i++) {
int to = graph[vtx][i];
if (to != from && removed[to] == false) {
DFS1(to, vtx, depth + 1, vec, minval, save);
size[vtx] += size[to];
}
}
}
void DFS2(int vtx, int from, int& size, int& center, int rootSize = -1) {
if (rootSize == -1) {
rootSize = ::size[vtx];
size = INF;
}
int maxSize = rootSize - ::size[vtx];
for (int i = 0; i < graph[vtx].size(); i++) {
int to = graph[vtx][i];
if (to != from && removed[to] == false) {
maxSize = std::max(maxSize, ::size[to]);
DFS2(to, vtx, size, center, rootSize);
}
}
if (maxSize < size) {
size = maxSize;
center = vtx;
}
}
int_t DFS3(int vtx) {
int center, size;
static std::vector<Data> vec;
DFS1(vtx, -1, 1, vec);
DFS2(vtx, -1, size, center);
int_t result = -INF;
removed[center] = true;
Node* root = new (allocate()) Node(-RANGE, RANGE);
static std::vector<Data> datas[LARGE + 1];
//正向两条路径
for (int _i = 0; _i < graph[center].size(); _i += 1) {
int to = graph[center][_i];
if (removed[to] == false) {
std::vector<Data>& curr = datas[_i];
curr.clear();
DFS1(to, -1, 1, curr, INF, true);
for (int i = 0; i < curr.size(); i++) {
//两条路径
const Data& thiz = curr[i];
//以分治中心为一个端点的答案
result = std::max(result, std::min((int_t)curr[i].val,
(int_t)::vals[center]) *
(curr[i].depth + 1));
result = std::max(
result,
((int_t)root->query(thiz.val, RANGE) + thiz.depth) * thiz.val);
}
for (int i = 0; i < curr.size(); i++) {
//加入答案
const Data& thiz = curr[i];
root->maxTo(std::min(thiz.val, ::vals[center]),
thiz.depth + 1);
}
}
}
//反向两条路径
used = 0;
root = new (allocate()) Node(-RANGE, RANGE);
for (int _i = graph[center].size() - 1; _i >= 0; _i -= 1) {
int to = graph[center][_i];
if (removed[to] == false) {
std::vector<Data>& curr = datas[_i];
for (int i = 0; i < curr.size(); i++) {
//两条路径
const Data& thiz = curr[i];
result = std::max(
result,
((int_t)root->query(thiz.val, RANGE) + thiz.depth) * thiz.val);
}
for (int i = 0; i < curr.size(); i++) {
//加入答案
const Data& thiz = curr[i];
root->maxTo(std::min(thiz.val,::vals[center]),
thiz.depth + 1);
}
}
}
//子树信息
for (int i = 0; i < graph[center].size(); i++) {
int to = graph[center][i];
if (removed[to] == false) {
result = std::max(result, DFS3(to));
}
}
used = 0;
removed[center] = false;
return result;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &vals[i]);
}
for (int i = 1; i <= n - 1; i++) {
int v1, v2;
scanf("%d%d", &v1, &v2);
graph[v1].push_back(v2);
graph[v2].push_back(v1);
}
printf("%lld", DFS3(1));
return 0;
}