自动搬运

查看原文

来自洛谷，原作者为

	asmend 。

搬运于2025-08-24 22:53:08，当前版本为作者最后更新于2023-12-18 09:02:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑列出整棵树的欧拉序，对于每个颜色 $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)$。

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

• 不要使用 vector，存图用前向星，按颜色归类用桶排。
• 特判链，此时不需要存图和 dfs 求欧拉序。
• dfs 到最后一个叶子之后，后面的欧拉序就不需要存了。
• 当 $m$ 很小时，不做分块预处理。

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]];
}