题解 P4211 【[LNOI2014]LCA】

· · 题解

大家都是树剖O(n*log^2_2n)的做法，那蒟蒻我就来一个O(n^{\frac{3}{2}})的做法.

首先,一个显然的想法:想要查询一个点和某些其他点的LCA深度和，我们可以考虑该节点的每个祖先中的需要查询的节点个数。但是会有重复统计，我们发现重复统计的次数即为LCA深度，所以我们显然地把问题转化成把所有要查询的节点到根的路径节点权值加1，查询某个节点的到根节点的路径权值和.

然后一个O(n^{\frac{3}{2}}*log^2_2n)的做法就出来了，用莫队维护区间，用树剖维护树上权值，期望的分20.

考虑优化，由于莫队每次更新的时间复杂度为O(log^2_2n)，但最多只有q次查询，可以考虑优化树剖的修改操作去掉一个log.但是这样还是过不了.

以上做法就达到莫队的极限了(大概).因为转移无法再优化了.然后我们发现某个静态的区间贡献的对于2某个查询贡献的答案是一定的，我们可以考虑分块.

对于每个块差分一下暴力dfs求出每个节点的答案.然后边角直接求LCA深度

然后LCA深度用倍增RMQ预处理即可做到O(1)查询

然后就做到整体O(n^{\frac{3}{2}})了.

代码如下(常数巨大):

#include<bits/stdc++.h>
using namespace std;
const int mod = 201314;

int n,m;
vector<int>to[50005];
int deep  [50005];

const int size = 500;
int belong[50005];
int query [105][50005];
int block [105];

int first[100005];
int st   [200005][18];
int lg2  [100005];
int cnt = 0;

void dfs_init(int now){
    st[ ++ cnt ][0] = deep[now];
    first[now] = cnt;
    for( auto next : to[now] ){
        deep[next] = deep[now] + 1;
        dfs_init( next );
        st[ ++ cnt ][0] = deep[now];
    }
}

int bin[50005];
void dfs1(int now){ for( auto next : to[now] )dfs1( next ),bin[now] += bin[next]; }
void dfs2(int now,int dist){ for( auto next : to[now] )dfs2( next,dist + bin[now] );bin[now] += dist; }

void init(){
    dfs_init(1);
    for(int i = 1;i <= n;i ++){
        belong[i] = i / size + 1;
        if( belong[i] - belong[i - 1] )block[ belong[i] ] = i;
    }
    for(int i = 2;i <= (n << 1);i ++)lg2[i] = lg2[i >> 1] + 1;
    for(int t = 1;t <= 17;t ++)for(int i = 1;i <= (n << 1) - (1 << t);i ++)
        st[i][t] = min( st[i][t - 1],st[i + (1 << (t - 1))][t - 1] );
}

int LCA(int A,int B){
    A = first[A];B = first[B];
    if( A > B )swap( A,B );
    int ln = lg2[ B - A + 1 ]; 
    return min( st[A][ln],st[B - (1 << ln) + 1][ln] );
}

int main(){
    cin >> n >> m;deep[1] = 1;
    for(int i = 2;i <= n;i ++){
        int v;cin >> v;v ++;
        to[v].push_back(i);
    }
    init();
    belong[0] = 0;belong[n + 1] = belong[n] + 1;
    block[0] = 0;block[ belong[n + 1] ] = n + 1;
    for(int i = 1;i <= belong[n];i ++){
        memset( bin,0,sizeof(bin) );
        for( int j = block[i];belong[j] == i;j ++ )bin[j] ++;
        dfs1(1);dfs2(1,0);
        for( int j = 1;j <= n;j ++ )query[i][j] = bin[j];
    }
    while( m -- ){
        int l,r,x;cin >> l >> r >> x;
        l ++;r ++;x ++;
        int bl = belong[l - 1] + 1;
        int br = belong[r + 1] - 1;
        long long ans = 0;
        for( ;belong[l] != bl and l <= r ;l ++ )ans += LCA( l,x );
        for( ;belong[r] != br and r >= l ;r -- )ans += LCA( r,x );
        for( int i = bl;i <= br;i ++ )ans += query[i][x];
        cout << ans % mod << "\n";
    }
    return 0;
}