11.01

ZepX-D / 2025-02-21 / 原文

今天的题至少有一个半可做，于是决定写个总结。

A.西克

唯一切的一道。
感觉题解离线点分治并查集很牛啊，一点都没想到。
所以我选择树剖倍增在线求。
好像跟 P7518 [省选联考 2021 A/B 卷] 宝石一模一样，可以移步阅读题面。

对于当前点 $x$，下一步有用的点 $y$ 为路径上第一个满足 $a_y=b_x$ 的点，可以假想他们之间连了一条边，那么询问变为从起点开始一直走边能跳到哪。
只是向上跳的话那么直接树上倍增就好了。
向下跳赛时唐了我半个小时，然后突然意识到树剖跳重链在重链上向下倍增就好了，时间复杂度 $O(n\log^2n)$，在线做法，但是由于树剖小 $\log$ 且随机数据一个点跳边的次数有限，所以跑的和题解单 $\log$ 一样快。

经过赛后搜索发现竟然和 yspm 大佬一个做法。

点击查看代码

#include <bits/stdc++.h>
#define fr first
#define se second
#define Un unsigned
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define __ __int128
#define ld long double
#define VE vector<LL>
#define db double
#define Ve vector<int>

using namespace std;

Un S1,S2;
Un rnd()
{
	S1 *= S2,S2 >>= S1&13,S2 -= S1,S1 ^= S2;
	return ((S1-S2)&(S1+S2))^(S1*S2>>4);
}

const int N = 2e6+5;
struct edge{int to,pre;}e[N<<1];
int las[N],cnt,a[N],b[N],fa[N],hs[N],siz[N],top[N],dep[N],ed[N],c[N],ct,pre[N],dip[N],dfn[N],d,tot,to[N];
Ve up[N],dwn[N],pos[N];

void add(int u,int v){e[++cnt] = {v,las[u]},las[u] = cnt;}

void D1(int x)
{
	dep[x] = dep[fa[x]]+1,siz[x] = 1;
	for (int i = las[x],y;i;i = e[i].pre)
	{
		D1(y = e[i].to),siz[x] += siz[y];
		if (siz[y] > siz[hs[x]]) hs[x] = y;
	}
}

void D2(int x,int t)
{
	dfn[x] = ++d,to[d] = x,top[x] = t,ed[t] = x;
	if (hs[x]) D2(hs[x],t);
	for (int i = las[x],y;i;i = e[i].pre)
		if ((y = e[i].to) != hs[x]) D2(y,y);
}

inline int findl(int l,int r,int x)
{
	int p = lower_bound(begin(pos[x]),end(pos[x]),l)-begin(pos[x]);
	if (p == pos[x].size() || pos[x][p] > r) return 0;
	return to[pos[x][p]];
}

inline int findr(int l,int r,int x)
{
	int p = upper_bound(begin(pos[x]),end(pos[x]),r)-begin(pos[x])-1;
	if (p == -1 || pos[x][p] < l) return 0;
	return to[pos[x][p]];
}

inline int Q(int x,int y)
{
	int p = x;
	vector < pii > D;
	while(top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) D.pb({top[y],y}),y = fa[top[y]];
		else
		{
			int k = findr(dfn[top[x]],dfn[x],b[p]);
			if (k)
			{
				p = k;
				if (up[p].size())
					for (int i = up[p].size()-1;i >= 0;i--)
						if (i < up[p].size()) p = up[p][i];
			}
			x = fa[top[x]];
		}
	}
	if (dep[x] < dep[y]) D.pb({x,y});
	else
	{
		int k = findr(dfn[y],dfn[x],b[p]);
		if (k)
		{
			p = k;
			if (up[p].size())
				for (int i = up[p].size()-1;i >= 0;i--)
					if (i < up[p].size() && dep[up[p][i]] >= dep[y]) p = up[p][i];
		}
	}
	for (int i = (int)D.size()-1;i >= 0;i--)
	{
		auto [l,r] = D[i];
		int k = findl(dfn[l],dfn[r],b[p]);
		if (k)
		{
			p = k;
			if (dwn[p].size())
				for (int j = dwn[p].size()-1;j >= 0;j--)
					if (j < dwn[p].size() && dep[dwn[p][j]] <= dep[r]) p = dwn[p][j];
		}
	}
	return b[p];
}

int main()
{
	int n,m;cin >> n >> m >> S1 >> S2;
	for (int i = 1;i <= min(n,500000);i++) cin >> a[i] >> b[i];
	for (int i = 500001;i <= n;i++)
	{
		a[i] = rnd()%n+1,b[i] = a[rnd()%500000+1];
		if (a[i] == b[i]) if (++a[i] > n) a[i] = 1;
	}
	for (int i = 2;i <= n;i++) cin >> fa[i],add(fa[i],i);
	D1(1),D2(1,1);
	for (int i = 1;i <= n;i++)
	{
		pos[a[i]].pb(dfn[i]);
		if (!ed[i]) continue;
		int p = ed[i];
		while(p != i) c[++ct] = p,p = fa[p];
		c[++ct] = p;
		for (int j = 1;j <= ct;j++)
		{
			if (pre[b[c[j]]])
			{
				dip[c[j]] = dip[pre[b[c[j]]]]+1;
				dwn[c[j]].resize(__lg(dip[c[j]])+1);
				dwn[c[j]][0] = pre[b[c[j]]];
				for (int k = 1;k <= __lg(dip[c[j]]);k++)
					dwn[c[j]][k] = dwn[dwn[c[j]][k-1]][k-1];
			}
			pre[a[c[j]]] = c[j];
		}
		for (int j = 1;j <= ct;j++) dip[c[j]] = pre[a[c[j]]] = 0;
		for (int j = ct;j >= 1;j--)
		{
			if (pre[b[c[j]]])
			{
				dip[c[j]] = dip[pre[b[c[j]]]]+1;
				up[c[j]].resize(__lg(dip[c[j]])+1);
				up[c[j]][0] = pre[b[c[j]]];
				for (int k = 1;k <= __lg(dip[c[j]]);k++)
					up[c[j]][k] = up[up[c[j]][k-1]][k-1];
			}
			pre[a[c[j]]] = c[j];
		}
		for (int j = 1;j <= ct;j++) dip[c[j]] = pre[a[c[j]]] = 0;
		ct = 0;
	}
	for (int i = 1;i <= n;i++) sort(begin(pos[i]),end(pos[i]));
	int ans = 0;
	while(m--)
	{
		int x,y;cin >> x >> y;
		ans ^= Q(x,y);
	}
	cout << ans;
	return 0;
}

空间仅用 $350MB$，建议把空间开成 $512MB$ 卡死空间大的。

C.苯为

只会暴力咋办？那就说下暴力吧。

首先会连成一棵基环树，发现答案仅跟环的长度有关，求出环的染色方案数之后其余点每个都可以填 $k-1$ 种颜色。
接下来有一个问题：一个长为 $n$ 的环，有 $k$ 种颜色，给每个节点涂上一种颜色使相邻的节点颜色两两不同的方案数。

我们设 $f_n$ 代表长为 $n$ 的环的合法染色方案数。首先一条链的方案数非常好求，为 $k(k-1)^{n-1}$。
链的首尾颜色可能相同或不同，相同即可看为一个长为 $n-1$ 的环的合法染色方案数，可得 $f_{n-1}+f_n=k(k-1)^{n-1}$，然后可以推柿子了。

\[\begin{aligned} f_{n-1}+f_n&=k(k-1)^{n-1}\\ f_{n-1}+f_n&=(k-1)^n+(k-1)^{n-1}\\ f_n-(k-1)^n&=-(f_{n-1}-(k-1)^{n-1}) \end{aligned} \]

令 $g_n=f_n-(k-1)^n$，则有 $\frac{g_n}{g_{n-1}}=-1$，为等比数列。
首先已知 $f_2=k(k-1)$，则 $g_2=f_2-(k-1)^2=k-1$，所以 $g_n=(-1)^n(k-1)=f_n-(k-1)^n$，可得 $f_n=(k-1)^n+(-1)^n(k-1)$，这样就会 $O(n^2)$ 暴力惹。
瓶颈在于求出对于每个 $i=1,\dots,n$ ，树上路径长度为 $i$ 的路径数量。

下面说下正解：
一个长度为 $n$ 的环的贡献为：$(k-1)^{n(A+1)}+(-1)^{n(A+1)}\times (k-1)$
那么最后答案为：

\[\begin{aligned} &\sum_{s}\sum_{t} ((k-1)^{d(A+1)+(-1)^{d(A+1)}(k-1)})\times (k-1)^{(n-d)(A+1)}\\ &=n^2\times (k-1)^{n(A+1)}+(k-1)\sum_{s}\sum_{t} (-1)^{d(A+1)}(k-1)^{(n-d)(A+1)} \end{aligned} \]

后面相当于给点带权，即环上点贡献为 $(-1)^{A+1}$，不在环上的点贡献为 $(k-1)^{A+1}$，树的点权积的和。
这个可以直接 dp，设 $f_x$ 为 $x$ 子树点权积之和，每次合并儿子即可。