lg9932 [NFLSPC #6] 树

· · 题解

考虑列出整棵树的欧拉序，对于每个颜色 c，设它出现了 m_c 次，那么它将欧拉序划分为 2m_c 个区间，每个区间答案相同。于是我们把问题转化为，有若干个有序数组，它们的长度之和为 O(n)，每次查询在其中一个数组中求 lower bound。直接对每次询问二分即可做到 O(n+q\log n)，可以获得约 [30,40] 分。

对每个数组，设数组中元素个数为 m，我们对欧拉序以 \frac{n}{m} 为块长分块，然后对块的端点预处理出 lower bound 的结果。查询时，找到查询位置所在块的端点，然后在此基础上暴力计算块内的部分。

由于颜色经过随机打乱，dfs 进栈序和出栈序都可视为均匀随机（尽管它们两个之间不独立），而欧拉序是进栈序和出栈序的某种归并，所以每块内期望有 O(1) 个元素。于是复杂度为 O(n+q)。

接下来还可以加一些常数优化，例如：

std 实现如下。

#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
#include "tree.h"
const int maxn=2000000;
int lg[maxn+5];
int n,i,j,dfn[maxn+5],lst[maxn+5],cc;
int a[maxn*2+5],c[maxn*2+5],cnt;
int fa[maxn+5],col[maxn+5];
int hd[maxn+5],nxt[maxn+5];
int _1[maxn*3+5],tot;
int *f[maxn+5];
int c0[maxn*2+5],s0[maxn*2+5];
int seq[maxn*2+5];
int len[maxn+5];
void dfs(int x)
{
    cc++;dfn[x]=++cnt;int mem=lst[col[x]];
    a[cnt]=col[x];c[cnt]=lst[col[x]]=x;
    int i;for(i=hd[x];i;i=nxt[i])dfs(i);
    cnt++;a[cnt]=col[x];c[cnt]=lst[col[x]]=mem;
}
void init(int nn,vector<int> fa1,vector<int> col1)
{
    n=nn;bool flg=1;
    fz0k(i,n)fa[i]=fa1[i],col[i]=col1[i],flg&=(fa[i]==i-1);
    fz(i,2,maxn)lg[i]=lg[i/2]+1;
    if(flg){
        cnt=n;
        fz0k(i,n){
            dfn[i]=i+1;
            a[i+1]=col[i];
            c[i+1]=i;
        }
    }
    else{
        fd1(i,n-1) nxt[i]=hd[fa[i]],hd[fa[i]]=i;
        fz0k(i,n)lst[i]=-1;
        dfs(0);
    }
    fz1(i,cnt) c0[a[i]]++;
    fz0k(i,n) s0[i]+=c0[i],s0[i+1]+=s0[i];
    fd1(i,cnt) seq[s0[a[i]]--]=i;
    fz0k(i,n)if(c0[i]>3){
        len[i]=lg[cnt/c0[i]];
        int len=(1<<::len[i]),num=(cnt>>::len[i]);
        f[i]=(_1+tot);tot+=num+1;
        int k=0;f[i][0]=0;
        fz1(j,num){
            while(k+1<=c0[i]&&seq[s0[i]+k+1]<=j*len) k++;
            f[i][j]=k;
        }
    }
}
int query(int x,int y)
{
    if(!c0[y]) return -1;x=dfn[x];
    int t=(c0[y]>3?f[y][x>>len[y]]:0);
    while(t+1<=c0[y]&&seq[s0[y]+t+1]<=x) t++;
    if(t==0) return -1; else return c[seq[s0[y]+t]];
}