【bzoj3251】树上三角形朴素LCA+暴力

题目描述

给定一大小为n的有点权树，每次询问一对点(u,v)，问是否能在u到v的简单路径上取三个点权，以这三个权值为边长构成一个三角形。同时还支持单点修改。

输入

第一行两个整数n、q表示树的点数和操作数

第二行n个整数表示n个点的点权

以下n-1行，每行2个整数a、b，表示a是b的父亲（以1为根的情况下）

以下q行，每行3个整数t、a、b

若t=0，则询问(a,b)

若t=1，则将点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

题解

朴素LCA+暴力

一开始想到了一个$O(n\log^3n)$的数据结构算法，然后发现自己太naive了= =

由于点权是int范围内的，所以如果想让尽量多的边不构成三角形，那么它们的边权应该为1、1、2、3、5、8、...

这显然是斐波那契数列，而斐波那契数列是指数增长的，到第50项左右就爆int了。

所以可以直接拿出两个点之间的路径，当拿出的超过50个时直接判定能构成三角形，否则排序，暴力。

时间复杂度为$O(q·50·\log 50)$

#include <cstdio>

#include <algorithm>

#define N 100010

using namespace std;

int w[N] , head[N] , to[N << 1] , next[N << 1] , cnt , fa[N] , deep[N] , a[100] , tot;

void add(int x , int y)

{

    to[++cnt] = y , next[cnt] = head[x] , head[x] = cnt;

}

void dfs(int x)

{

    int i;

    for(i = head[x] ; i ; i = next[i])

        if(to[i] != fa[x])

            fa[to[i]] = x , deep[to[i]] = deep[x] + 1 , dfs(to[i]);

}

bool judge(int x , int y)

{

    int i;

    tot = 0;

    if(deep[x] < deep[y]) swap(x , y);

    while(deep[x] > deep[y])

    {

        a[++tot] = w[x] , x = fa[x];

        if(tot > 50) return 1;

    }

    while(x != y)

    {

        a[++tot] = w[x] , a[++tot] = w[y] , x = fa[x] , y = fa[y];

        if(tot > 50) return 1;

    }

    a[++tot] = w[x] , sort(a + 1 , a + tot + 1);

    for(i = 3 ; i <= tot ; i ++ )

        if(a[i] - a[i - 1] < a[i - 2])

            return 1;

    return 0;

}

int main()

{

    int n , m , i , opt , x , y;

    scanf("%d%d" , &n , &m);

    for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]);

    for(i = 1 ; i < n ; i ++ ) scanf("%d%d" , &x , &y) , add(x , y) , add(y , x);

    dfs(1);

    while(m -- )

    {

        scanf("%d%d%d" , &opt , &x , &y);

        if(opt) w[x] = y;

        else if(judge(x , y)) puts("Y");

        else puts("N");

    }

    return 0;

}

巴特西

【bzoj3251】树上三角形朴素LCA+暴力

最新文章

热门文章

巴特西

【bzoj3251】树上三角形 朴素LCA+暴力

最新文章

热门文章

【bzoj3251】树上三角形朴素LCA+暴力