BZOJ3251树上三角形

这题居然和斐波那契数列有关系。。。

考虑一下，如果把斐波那契数视为一个集合，那么这个集合的任意子集一定不能够拿出来三个数让他们作为三角形的三边。

考虑到这题目里的点权不超过$2^{31}-1$,这个范围内的斐波那契数只有52个。

我们可以断言，在一条路径长度超过52时，那么这条路径一定不可能是斐波那契数集合的一个子集。

对于路径长度小于52的情况,$n^3$暴力。

#include <inttypes.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
typedef int int_t;
using std::cin;
using std::cout;
using std::endl;

const int_t LIMIT = 52;
const int_t LARGE = 1e5;
int_t parent[LARGE + 1];
int_t vals[LARGE + 1];
std::vector<int_t> graph[LARGE + 1];
struct State {
    int_t vertex;
    int_t depth;
    State(int_t vertex = -1, int_t depth = 0) {
        this->depth = depth;
        this->vertex = vertex;
    }
    bool operator<(const State& state) const { return depth < state.depth; }
} seq[20][LARGE * 2 + 10];
int_t first[LARGE + 1];
int_t depth[LARGE + 1];
int_t count = 0;
int n, q;
void DFS(int_t vtx, int_t depth = 1, int_t from = -1) {
    seq[0][++count] = State(vtx, depth);
    if (first[vtx] == 0) first[vtx] = count;
    ::depth[vtx] = depth;
    ::parent[vtx] = from;
    for (int_t i = 0; i < graph[vtx].size(); i++) {
        int_t to = graph[vtx][i];
        if (to != from) {
            DFS(to, depth + 1, vtx);
            seq[0][++count] = State(vtx, depth);
        }
    }
}
int queryLCA(int v1, int v2) {
    v1 = first[v1];
    v2 = first[v2];
    if (v1 > v2) std::swap(v1, v2);
    int_t len = log2(v2 - v1 + 1);
    return std::min(seq[len][v1], seq[len][v2 - (1 << len) + 1]).vertex;
}
int main() {
    scanf("%d%d", &n, &q);
    for (int_t i = 1; i <= n; i++) {
        scanf("%d", &vals[i]);
    }
    for (int_t i = 1; i <= n - 1; i++) {
        int v1, v2;
        scanf("%d%d", &v1, &v2);
        graph[v1].push_back(v2);
    }
    DFS(1);
    for (int i = 1; (1 << i) <= count; i++) {
        for (int j = 1; j + (1 << i) - 1 <= count; j++) {
            seq[i][j] = std::min(seq[i - 1][j], seq[i - 1][j + (1 << (i - 1))]);
        }
    }
    for (int i = 1; i <= q; i++) {
        int t, a, b;
        scanf("%d%d%d", &t, &a, &b);
        if (t == 0) {
            int_t lca = queryLCA(a, b);
            int_t len = depth[a] + depth[b] - 2 * depth[lca] + 1;
            if (len > LIMIT) {
                puts("Y");
            } else {
                std::vector<int_t> vals;
                while (a != lca) {
                    vals.push_back(::vals[a]);
                    a = parent[a];
                }
                while (b != lca) {
                    vals.push_back(::vals[b]);
                    b = parent[b];
                }
                vals.push_back(::vals[lca]);
#ifdef DEBUG
                cout << "vals "
                     << " ";
                for (int_t x : vals) cout << x << " ";
                cout << endl;
#endif
                std::sort(vals.begin(), vals.end());
                bool flag = false;
                for (int_t i = 0; i < vals.size() && !flag; i++) {
                    for (int_t j = i + 1; j < vals.size() && !flag; j++) {
                        for (int_t k = j + 1; k < vals.size() && !flag; k++) {
                            if ((int64_t)vals[i] + (int64_t)vals[j] >
                                (int64_t)vals[k]) {
                                flag = true;
                            }
                        }
                    }
                }
                if (flag)
                    puts("Y");
                else
                    puts("N");
            }
        } else {
            vals[a] = b;
        }
    }
    return 0;
}