树链剖分 + 后缀数组 - E. Misha and LCP on Tree

2024-09-05 16:58
文章标签 数组 后缀 tree 树链 剖分 lcp misha

本文主要是介绍树链剖分 + 后缀数组 - E. Misha and LCP on Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

E. Misha and LCP on Tree 

Problem's Link

 

Mean: 

给出一棵树，每个结点上有一个字母。每个询问给出两个路径，问这两个路径的串的最长公共前缀。

analyse:

做法：树链剖分+后缀数组.

记录每条链的串，正反都需要标记，组成一个长串.

然后记录每条链对应的串在大串中的位置,对大串求后缀数组,最后询问就是在一些链上的查询。

Time complexity: O(n*logn)

 

view code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 300005
#define BB 1145143
#define MOD 1000000007
#define BT 20

using namespace std;
typedef long long int ll;

vector < int > vec [ SIZE ];
vector < int > get [ SIZE ];
int par [ SIZE ][ BT ], dep [ SIZE ];
ll hash1 [ SIZE ], hash2 [ SIZE ], rt [ SIZE ];
int nd [ SIZE ], nxt [ SIZE ], id [ SIZE ], pos [ SIZE ];
int n1 [ SIZE ], n2 [ SIZE ];
char str [ SIZE ];
int n , m;

void dfs( int v = 0 , int p =- 1 , int d = 0 , ll h1 = 0 , ll h2 = 0)
{
    par [ v ][ 0 ] =p;
    dep [ v ] = d;
    h1 *=BB;
    hash1 [ v ] = h1 +( str [ v ] - 'a' + 1);
    hash2 [ v ] = h2 +( ll) ( str [ v ] - 'a' + 1) * rt [ d ];
    hash1 [ v ] %= MOD;
    hash2 [ v ] %= MOD;
    nd [ v ] = 1;
    for( int i = 0; i < vec [ v ]. size(); i ++)
    {
        int to = vec [ v ][ i ];
        if( to !=p)
        {
            dfs( to , v , d + 1 , hash1 [ v ], hash2 [ v ]);
            nd [ v ] += nd [ to ];
        }
    }
}
void make()
{
    for( int i = 0; i < BT - 1; i ++)
    {
        for( int j = 0; j <n; j ++)
        {
            if( par [ j ][ i ] ==- 1) par [ j ][ i + 1 ] =- 1;
            else par [ j ][ i + 1 ] = par [ par [ j ][ i ]][ i ];
        }
    }
}
ll get1( int s , int t)
{
    int p = par [ t ][ 0 ];
    return ( hash1 [s ] -(p ==- 1 ? 0 : hash1 [p ] * rt [ dep [s ] - dep [p ]] % MOD) + MOD) % MOD;
}
ll get2( int s , int t)
{
    int p = par [s ][ 0 ];
    return ( hash2 [ t ] -(p ==- 1 ? 0 : hash2 [p ]) + MOD) % MOD;
}
int LCA( int a , int b)
{
    if( dep [ a ] > dep [b ]) swap( a ,b); //dep[a]<=dep[b]
    for( int i = BT - 1; i >= 0; i --)
    {
        if( par [b ][ i ] ==- 1|| dep [ par [b ][ i ]] < dep [ a ]) continue;
       b = par [b ][ i ];
    }
    if( a ==b) return a;
    for( int i = BT - 1; i >= 0; i --)
    {
        if( par [ a ][ i ] != par [b ][ i ])
        {
            a = par [ a ][ i ];
           b = par [b ][ i ];
        }
    }
    return par [ a ][ 0 ];
}
int sz;
void heavy_light( int v = 0 , int p =- 1 , int last =- 1)
{
    bool up = false;
    pos [ v ] = sz;
    id [ v ] = get [ sz ]. size();
    nxt [ v ] = last;
    get [ sz ]. push_back( v);
    for( int i = 0; i < vec [ v ]. size(); i ++)
    {
        int to = vec [ v ][ i ];
        if( to !=p && nd [ to ] * 2 >= nd [ v ])
        {
            heavy_light( to , v , last);
            up = true;
            break;
        }
    }
    if( ! up) sz ++;
    for( int i = 0; i < vec [ v ]. size(); i ++)
    {
        int to = vec [ v ][ i ];
        if( to !=p && nd [ to ] * 2 < nd [ v ])
        {
            heavy_light( to , v , v);
        }
    }
}
int main()
{
    scanf( "%d" , &n);
    scanf( "%s" , & str);
    for( int i = 0; i <n - 1; i ++)
    {
        int a ,b;
        scanf( "%d %d" , & a , &b);
        a --;
       b --;
        vec [ a ]. push_back(b);
        vec [b ]. push_back( a);
    }
    rt [ 0 ] = 1;
    for( int i = 1; i < SIZE; i ++) rt [ i ] = rt [ i - 1 ] *( ll) BB % MOD;
    dfs();
    make();
    heavy_light(); /*
   printf("%d\n",sz);
   for(int i=0;i<sz;i++)
   {
       for(int j=0;j<get[i].size();j++) printf("%d ",get[i][j]);
       puts("");
   }*/
    int m;
    scanf( "%d" , & m);
    for( int i = 0; i < m; i ++)
    {
        int a ,b , c , d;
        scanf( "%d %d %d %d" , & a , &b , & c , & d);
        a --;
       b --;
        c --;
        d --;
        if( str [ a ] != str [ c ])
        {
            puts( "0");
            continue;
        }
        int p = LCA( a ,b ), q = LCA( c , d);
        if( dep [ a ] - dep [p ] > dep [ c ] - dep [ q ])
        {
            swap( a , c);
            swap(b , d);
            swap(p , q);
        }
        int A =b , bef =- 1;
        while( A !=- 1)
        {
            n1 [ pos [ A ]] = bef;
            bef = get [ pos [ A ]][ 0 ];
            A = nxt [ A ];
        }
        int C = d;
        bef =- 1;
        while( C !=- 1)
        {
            n2 [ pos [ C ]] = bef;
            bef = get [ pos [ C ]][ 0 ];
            C = nxt [ C ];
        }
        bool up = true;
        int ret = 1;
        while( a !=p)
        {
            int ta = nxt [ a ];
            if( ta ==- 1|| dep [ ta ] < dep [p ]) ta =p;
            int tc = nxt [ c ];
            if( tc ==- 1|| dep [ tc ] < dep [ q ]) tc = q;
            int la = dep [ a ] - dep [ ta ], lc = dep [ c ] - dep [ tc ];
            int ml = min( la , lc);
            int va = ml == la ? ta: get [ pos [ a ]][ id [ a ] - ml ];
            int vc = ml == lc ? tc: get [ pos [ c ]][ id [ c ] - ml ];
            if( get1( a , va) != get1( c , vc))
            {
                int s =- 1 , e = ml;
                while( e -s > 1)
                {
                    int m =(s + e) / 2;
                    va = get [ pos [ a ]][ id [ a ] - m ];
                    vc = get [ pos [ c ]][ id [ c ] - m ];
                    if( get1( a , va) != get1( c , vc)) e = m;
                    else s = m;
                }
                ret +=s;
                up = false;
                break;
            }
            ret += ml;
            a = va;
            c = vc;
        }
        if( ! up)
        {
            printf( "%d \n " , ret);
            continue;
        }
        while( c != q && a !=b)
        {
            int ta = n1 [ pos [ a ]];
            if( ta ==- 1|| dep [ ta ] > dep [b ]) ta =b;
            int tc = nxt [ c ];
            if( tc ==- 1|| dep [ tc ] < dep [ q ]) tc = q;
            int la = dep [ ta ] - dep [ a ], lc = dep [ c ] - dep [ tc ];
            int ml = min( la , lc);
            int va = ml == la ? ta: get [ pos [ a ]][ id [ a ] + ml ];
            int vc = ml == lc ? tc: get [ pos [ c ]][ id [ c ] - ml ];
            if( get2( a , va) != get1( c , vc) * rt [ dep [ a ]] % MOD)
            {
                int s =- 1 , e = ml;
                while( e -s > 1)
                {
                    int m =(s + e) / 2;
                    va = get [ pos [ a ]][ id [ a ] + m ];
                    vc = get [ pos [ c ]][ id [ c ] - m ];
                    if( get2( a , va) != get1( c , vc) * rt [ dep [ a ]] % MOD) e = m;
                    else s = m;
                }
                ret +=s;
                up = false;
                break;
            }
            ret += ml;
            a = va;
            c = vc;
        }
        if( ! up)
        {
            printf( "%d \n " , ret);
            continue;
        }
        while( a !=b && c != d)
        {
            int ta = n1 [ pos [ a ]];
            if( ta ==- 1|| dep [ ta ] > dep [b ]) ta =b;
            int tc = n2 [ pos [ c ]];
            if( tc ==- 1|| dep [ tc ] > dep [ d ]) tc = d;
            int la = dep [ ta ] - dep [ a ], lc = dep [ tc ] - dep [ c ];
            int ml = min( la , lc);
            int va = ml == la ? ta: get [ pos [ a ]][ id [ a ] + ml ];
            int vc = ml == lc ? tc: get [ pos [ c ]][ id [ c ] + ml ];
            if( get2( a , va) * rt [ dep [ c ]] % MOD != get2( c , vc) * rt [ dep [ a ]] % MOD)
            {
                int s =- 1 , e = ml;
                while( e -s > 1)
                {
                    int m =(s + e) / 2;
                    va = get [ pos [ a ]][ id [ a ] + m ];
                    vc = get [ pos [ c ]][ id [ c ] + m ];
                    if( get2( a , va) * rt [ dep [ c ]] % MOD != get2( c , vc) * rt [ dep [ a ]] % MOD) e = m;
                    else s = m;
                }
                ret +=s;
                up = false;
                break;
            }
            ret += ml;
            a = va;
            c = vc;
        }
        printf( "%d \n " , ret);
    }
    return 0;
}

这篇关于树链剖分 + 后缀数组 - E. Misha and LCP on Tree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1139542。

相关文章

C++初始化数组的几种常见方法(简单易懂)

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化（推荐方式）1.2、初始化部分列表1.3、使用std::
阅读更多...
C++ Primer 多维数组的使用

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没
阅读更多...
Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
Python在固定文件夹批量创建固定后缀的文件(方法详解)

Python在固定文件夹批量创建固定后缀的文件(方法详解)

《Python在固定文件夹批量创建固定后缀的文件(方法详解)》文章讲述了如何使用Python批量创建后缀为.md的文件夹,生成100个,代码中需要修改的路径、前缀和后缀名,并提供了注意事项和代码示例,... 目录1. python需求的任务2. Python代码的实现3. 代码修改的位置4. 运行结果5.
阅读更多...
JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

JAVA中整型数组、字符串数组、整型数和字符串 的创建与转换的方法

《JAVA中整型数组、字符串数组、整型数和字符串的创建与转换的方法》本文介绍了Java中字符串、字符数组和整型数组的创建方法,以及它们之间的转换方法,还详细讲解了字符串中的一些常用方法,如index... 目录一、字符串、字符数组和整型数组的创建1、字符串的创建方法1.1 通过引用字符数组来创建字符串1.2
阅读更多...
vue如何监听对象或者数组某个属性的变化详解

vue如何监听对象或者数组某个属性的变化详解

《vue如何监听对象或者数组某个属性的变化详解》这篇文章主要给大家介绍了关于vue如何监听对象或者数组某个属性的变化,在Vue.js中可以通过watch监听属性变化并动态修改其他属性的值,watch通... 目录前言用watch监听深度监听使用计算属性watch和计算属性的区别在vue 3中使用watchE
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu 1166 敌兵布阵（树状数组 or 线段树）

hdu 1166 敌兵布阵（树状数组 or 线段树）

题意是求一个线段的和，在线段上可以进行加减的修改。 树状数组的模板题。 代码： #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C 语言基础之数组

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组，顾名思义，就是一组数。 假如班上有 30 个同学，让你编程统计每个人的分数，求最高分、最低分、平均分等。如果不知道数组，你只能这样写代码： int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2