(第一种情况即 $LCA(k)$ 的祖先为根节点 $1$ ，即 $LCA(k)$ 为该子树的根时)
那么在枚举到 $b$ 时，对哈希函数的贡献可计算为
$$Y^b\sum _{i=2}^{p}su{m}_{LCA(i)}$$

其中与 $a$ 有关的项可展开为:
Y b ( X a Z L C A ( 2 ) + X a Z L C A ( 3 ) − X a Z L C A ( 2 ) + . . . + X a Z L C A ( p ) − X a Z L C A ( p − 1 ) ) = Y b X a Z L C A ( p )

与哈希函数中的形式相同，这正是我们想要的。
最坏情况下子树退化为链，此时对于每个节点枚举祖先的复杂度为 $O(n)$ ，计算子树内贡献的复杂度为 $O(n^2)$ 。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

#define ll long long
const int MAXN=55,MAXT=4e4+5,P=998244353;
int n=50;
ll F,X,Y,Z;
ll pX[MAXN],pY[MAXN],pZ[MAXN];//幂表
ll sum[MAXN];//辅助数组,用于计算哈希值

int f[MAXN];//存储当前计算的子树
int Fa[MAXT][MAXN];//用于存储左子树

int stk[MAXN],top;//一个栈,用于维护祖先
vector<int>A,B;//左/右子树
map<int,int>mp;//记录对于一个哈希值,是否存在对应的左子树

void init(){
	pX[0]=pY[0]=pZ[0]=1;
	for(int i=1;i<=n;++i){//对X,Y,Z的幂进行打表
		pX[i]=pX[i-1]*X%P;
		pY[i]=pY[i-1]*Y%P;
		pZ[i]=pZ[i-1]*Z%P;
	}
	vector<int>().swap(A);
	vector<int>().swap(B);
	for(int i=2;i<=n/2;++i){
		A.push_back(i);//左子树
		F=(F-X*pY[i]%P*Z)%P;//左子树内每个点与根的贡献
	}
	for(int i=n/2+1;i<=n;++i){
		B.push_back(i);//右子树
		F=(F-X*pY[i]%P*Z)%P;//右子树内每个点与根的贡献
	}
	for(int i=0;i<A.size();++i){
		for(int j=0;j<B.size();++j){
			int x=A[i],y=B[j];
			F=(F-pX[x]*pY[y]%P*Z)%P;//左右子树间(LCA为根节点1)的贡献
		}
	}
	F=(F+P)%P;//可能为负,注意化为正数
	mp.clear();//清空原先的左子树可能哈希值
}

void Rand(vector<int>V){//以V中节点随机生成一棵树
	f[V[0]]=1;
	for(int i=1;i<V.size();++i){
		f[V[i]]=V[rand()%i];//选取一个下标小于他的作为父亲,保证最终构成一棵树
	}
}

int Hash(vector<int>V){//计算V构成的树内部的哈希值
	int ret=0;
	memset(sum,0,sizeof(sum));//初始化
	sort(V.begin(),V.end());//根据标号从小到大
	for(int i=0,u,v;i<V.size();++i){
		u=v=V[i],top=0;
		while(v!=1){
			stk[++top]=v;v=f[v];//用栈存储它的祖先们
		}
		int pre=0,now;
		while(top){
			v=stk[top--];
			ret=(ret+pY[u]*sum[v])%P;//计算对哈希值的贡献
			now=pX[u]*pZ[v]%P;
			sum[v]=(sum[v]+now-pre)%P;//更新sum数组
			pre=now;
		}
	}
	return (ret+P)%P;//因为sum数组在过程中可能为负数,所以ret也可能为负数,注意化为正数
}

int main()
{
	int T;read(T);
	while(T--){
		read(F),read(X),read(Y),read(Z);
		init();
		for(int t=1;t<MAXT;++t){
			Rand(A);//枚举40000次左子树
			int val=Hash(A);
			mp[val]=t;//记录下该棵左子树的哈希值
			memcpy(Fa[t],f,sizeof(f));//存下这课左子树
		}
		while(1){
			Rand(B);//枚举右子树
			int val=(F-Hash(B)+P)%P;//需要的左子树哈希值
			if(mp.find(val)!=mp.end()){//存在对应的左子树
				int t=mp[val];
				for(int i=2;i<=n/2;++i)f[i]=Fa[t][i];//将左子树取出
				break;
			}
		}
		cout<<n<<'\n';
		for(int i=2;i<=n;++i)cout<<f[i]<<' '<<i<<'\n';//输出每个点的父亲到它的这条边,即输出一棵树
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106