猫树

牛客多校比赛的时候碰到了一题

https://ac.nowcoder.com/acm/contest/11257/K

其实原理比较简单

用于$O(1)$查询树上的一些询问

方法大概是点分治之后建出点分树

每一条链的答案可以在把他们分成两个子树的那个位置查询

代码里写的查询是$loglogn$的实测会快于$rmq$的$lca$

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

//#include <immintrin.h>
//#include <emmintrin.h>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define ll long long
#define me(x) memset(x,0,sizeof(x))
#define IL inline
#define rint register int
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c=='-')f=1;c=getchar();}
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return f?-x:x;
}
char ss[1<<24],*A=ss,*B=ss;
IL char gc()
{
    return A==B&&(B=(A=ss)+fread(ss,1,1<<24,stdin),A==B)?EOF:*A++;
}
template<class T>void maxa(T &x,T y)
{
    if (y>x) x=y;
}
template<class T>void mina(T &x,T y)
{
    if (y<x) x=y;
}
template<class T>void read(T &x)
{
    int f=1,c; while (c=gc(),c<48||c>57) if (c=='-') f=-1; x=(c^48);
    while(c=gc(),c>47&&c<58) x=x*10+(c^48); x*=f;
}
const int mo=1e9+7;
ll fsp(int x,int y)
{
    if (y==1) return x;
    ll ans=fsp(x,y/2);
    ans=ans*ans%mo;
    if (y%2==1) ans=ans*x%mo;
    return ans;
}
struct cp {
    ll x,y;
    cp operator +(cp B)
    {
        return (cp){x+B.x,y+B.y};
    }
    cp operator -(cp B)
    {
        return (cp){x-B.x,y-B.y};
    }
    ll operator *(cp B)
    {
        return x*B.y-y*B.x;
    }
    int half() { return y < 0 || (y == 0 && x < 0); }
};
struct re{
    int a,b,c;
};
int n,m,seed,sum,rt;
struct Rand{
    unsigned int n,seed;
    Rand(unsigned int n,unsigned int seed)
    :n(n),seed(seed){}
    int get(long long lastans){
        seed ^= seed << 13;
        seed ^= seed >> 17;
        seed ^= seed << 5;
        return (seed^lastans)%n+1;
    }
};
const int N=1e6;
int son[N],f[N];
vector<int> ve[N];
int D,R;
ll bz[N][21],dp[N][2][2],dp2[N][21][2],a[N];
bool vis[N]; 
void gr(int x,int y)
{
    son[x]=1; f[x]=0;
    for (auto v:ve[x])
      if (!vis[v]&&v!=y)
      {
          gr(v,x);
          son[x]+=son[v];
          f[x]=max(f[x],son[v]);
      }
    f[x]=max(f[x],sum-son[x]);
    if (f[x]<f[rt]) rt=x;
}
void DP(int x,int y)
{
    bz[x][D]=R;
    dp2[x][D][0]=max(dp[x][0][0],dp[x][0][1]);
    dp2[x][D][1]=max(dp[x][1][0],dp[x][1][1]);
    for (auto v:ve[x])
    if (v!=y&&!vis[v])
    {
        rep(o,0,1)
        {
          dp[v][o][0]=max(dp[x][o][1],dp[x][o][0]);
          dp[v][o][1]=a[v]+dp[x][o][0];
        }
        DP(v,x);
    }
}
void solve(int x,int dep)
{
    if (dep>20)
    {
        while (1){};
    }
    vis[x]=1; D=dep; R=x;
    dp[x][0][0]=dp[x][0][1]=dp[x][1][0]=0;
    dp[x][1][1]=a[x];
    DP(x,0);
    for (auto v:ve[x])
      if (!vis[v])
      {
          rt=0; sum=son[v];
          gr(v,x);
          solve(rt,dep+1);
      }
}
ll query(int x,int y)
{
    int h=0,t=20;
    while (h<t)
    {
        int midd=(h+t+1)/2;
        if (bz[x][midd]!=0&&bz[x][midd]==bz[y][midd]) h=midd;
        else t=midd-1; 
    }
    return max(dp2[x][h][0]+dp2[y][h][0],dp2[x][h][1]+dp2[y][h][1]-a[bz[x][h]]);
}
int main()
{
   ios::sync_with_stdio(false);
   n=rd(); m=rd(); seed=rd();
   rep(i,1,n) a[i]=rd();
   rep(i,2,n)
   {
        int x;
        x=rd();
        ve[i].push_back(x);
     ve[x].push_back(i); 
   }
   long long lastans=0,ans=0;
   constexpr int P=998244353;
   Rand r(n,seed);
   sum=n; 
   f[0]=1e9;
   gr(1,0);
   solve(rt,0);
   rep(i,1,m)
   {
           int u=r.get(lastans);
        int v=r.get(lastans);
        int x=r.get(lastans);
        lastans=query(u,v);//calculate the answer
        ans=(ans+lastans%P*x)%P;
   }
   cout<<ans<<endl;
   return 0;
}

View Code

这题zzk有一种比较奇妙的做法

考虑直接树剖之后相当于要维护转移矩阵

直接暴力是$log^2$的

考虑现在我们利用类似rmq求区间最大值的方法求这一段矩阵的乘积

由于rmq两段有相互覆盖，没有办法处理

我们可以使用一种科技

对于每个$len=2^i$,求一下$len，2*len,...$求一下它往左右扩展$len$的长度时的矩阵乘积

然后查询$x,y$的时候

可以证明答案一定在$highbit(x^y)$的答案里，$highbit(x)$代表$x$的最高位