忧桑三角形

题目描述

小 J 是一名 OI 退役滚粗文化课选手, 他十分喜欢做题, 尤其是裸题. 有一棵树, 树上每个点都有点权, 现在有以下两个操作:

  1. 修改某个点的点权
  2. 查询点 u 和点 v 构成的简单路径上是否能选出三个点组成三角形

输入格式

第一行两个整数 \(N,Q\), 代表点数和询问数. 第二行 \(N\) 个整数表示点权. 下面 \(N - 1\) 行每行两个整数 \(a, b\) 代表 \(a, b\) 之间有一条边. 下面 \(Q\) 行每行 3 个整数 \(t, a, b\): 若 \(t = 0\), 询问 \((a, b)\); 否则将点 \(a\) 的权值修改为 \(b\).

输出格式

对于每个询问输出Y 表示能构成三角形, 输出N 表示不能构成三角形

样例输入

5 5
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3

样例输出

N
Y
Y
N

数据范围

对于 30% 的数据有 \(N, Q \leq 1000\)

对于 100% 的数据有 \(N, Q \leq 10^5\), 点权范围在 32 位整数范围内

Explanation

如果要保证一群数互相不构成三角形数, 需要保证:

  1. 将这群数从到大小排序,
  2. \(\forall i \in [0, n - 2], S_i + S_{i+1} <= S_{i+2}\)
  3. 所以这个数组必定上升快于斐波那契数列.

因为斐波那契数列 \(F_45 \approx 2^{32}\):

所以大概搜完超过 45 个点就可以停止搜索并且 return true 了.

否则按照规定拍一下序, 然后瞎搞一发.

这个想法是 @Burst_Zero 大神告诉我的.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 100100;

class XiaGaoTree
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    } *edges[maxn], epool[maxn * 2];
    int depth[maxn];
    int parent[maxn];
    int n, ecnt;
    lli value[maxn];
    void addedge(int u, int v)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        q->u = v; q->v = u;
        q->next = edges[v]; edges[v] = q;
        return ;
    }
    void bfs(void)
    {
        queue<int> que;
        que.push(1);
        depth[1] = 1;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (!depth[ep->v]) {
                    depth[ep->v] = depth[p] + 1;
                    parent[ep->v] = p;
                    que.push(ep->v);
                }
        }
        return ;
    }
    void change(int p, lli val)
    {
        value[p] = val;
        return ;
    }
    bool query(int p, int q)
    {
        vector<lli> vec;
        int cnt = 0;
        while (p != q) {
            // printf("dbfs %d %d\n", p, q);
            if (depth[p] >= depth[q]) {
                vec.push_back(value[p]);
                p = parent[p];
            } else {
                vec.push_back(value[q]);
                q = parent[q];
            }
            cnt++;
            if (cnt >= 50)
                return true;
        }
        vec.push_back(value[p]);
        sort(vec.begin(), vec.end());
        // for (int i = 0; i < vec.size(); i++)
        //     cout << vec[i] << ' ';
        // cout << endl;
        for (int i = 0; i < (int)vec.size() - 2; i++)
            if (vec[i] + vec[i + 1] > vec[i + 2])
                return true;
        return false;
    }
} graph;

int n, q;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &graph.value[i]);
    for (int i = 1, a, b; i < n; i++) {
        scanf("%d%d", &a, &b);
        graph.addedge(a, b);
    }
    graph.n = n;
    graph.bfs();
    for (int i = 1; i <= q; i++) {
        int a, b; lli c;
        scanf("%d%d%lld", &a, &b, &c);
        if (a == 0) {
            printf("%s\n", graph.query(b, c) ? "Y" : "N");
        } else {
            graph.change(b, c);
        }
    }
    return 0;
}