BZOJ 2870 最长道路

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;
}