自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:11:48，当前版本为作者最后更新于2021-10-27 08:45:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

全文链接：https://www.luogu.com.cn/blog/ix-35/xr-3-zuo-ti-ji-lu

这里有一种和已有题解不完全一样的做法。

E. Namid[A]me

难度：$\bigstar\bigstar\bigstar$​

题目大意：

给定 $n$ 个点的点带权树，设其叶子（度数为 $1$ 的点）个数为 $d$，点 $i$ 的权值为 $a_i$，令 $f(u,v)$ 为 $u\to v$ 路径上点权与，对所有无序对 $(u,v)$ 求和 $f(u,v)^{f(u,v)}$，答案对 $786433$ 取模，模数有一个原根是 $10$​。

$1\leq n\leq 2\times 10^5,\ \ a_i<2^{30},\ \ 1\leq n\times d\leq 3\times 10^6$​

题目解法：

显然树中的任意一条路径是以某个叶子为根时的一段祖先链，我们不妨依次枚举叶子 $l_1,\ldots,l_d$ 为根，统计祖先链的贡献。

对于确定的 $u$，枚举其祖先 $v$ 的过程中，显然 $f(u,v)$ 只有不超过 $\log A$ 种取值（$A$ 是 $a_i$ 的上界），并且在 DFS 过程中对每一位记录最深的这一位为 $0$ 的点就可以得到这 $\log A$ 种值和它们的分界点，于是只需要 $O(n\log A)$ 就可以统计所有祖先链的答案。

但是这样会重复计算，所以我们不妨让 $l_i$ 为根时不再计算在 $l_1,\ldots,l_{i-1}$ 为根时已经计算过的那些路径。

设祖先链是 $u\to v$（$v$ 是祖先，$u$ 是后代），再设 $w$ 是 $v$ 到 $u$ 路径上 $v$ 的后继点，那么这条祖先链之前没有被算过，当且仅当 $l_1,\ldots,l_{i-1}$ 都在 $w$ 的子树中，且都不在 $u$ 的子树中，也就是说我们只是对 $u$ 的选取进行限制，然后再限制 $v$ 是 $u$ 的深度不超过一个定值的祖先，还是可以用与上面相同的 DFS 方法求解。

注意利用原根使得幂的计算变为 $O(1)$ 的。

时间复杂度为 $O(dn\log A)$。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010,P=786433;
int n,x,y,cnt,nw,ans,lf[MAXN],a[MAXN],b[MAXN],dp[MAXN];
int lg[P+10],ex[P+10],f[MAXN],dep[MAXN],srt[MAXN];
pair <int,int> las[MAXN][32];
vector <int> v[MAXN];
bool cmp (pair <int,int> a,pair<int,int> b) {return a.first>b.first;}
int calc (int x) {
	if (x%P==0) {return 0;}
	return ex[(1ll*x*lg[x%P])%(P-1)];
}
void gt (int a,int b) {
	//cout << "    " << a << "  " << b << "  ";
	int tmp=dep[b];
	if (!srt[b]) {
		sort(las[b],las[b]+30,cmp);
		srt[b]=1;
	}
	for (int i=0;i<30;i++) {
		ans=(ans+(1ll*calc(a)*(tmp-las[b][i].first))%P)%P;
		tmp=las[b][i].first;
		if (a&(1<<las[b][i].second)) {a^=(1<<las[b][i].second);}
	}
	//cout << ans << endl;
	return;
}
void dfs1 (int x,int fa) {
	dp[x]=b[x],f[x]=fa,dep[x]=dep[fa]+1,srt[x]=0;
	for (int i=0;i<30;i++) {
		las[x][i]=las[fa][i];
		if (!(a[x]&(1<<i))) {las[x][i]=make_pair(dep[x],i);}
	}
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==fa) {continue;}
		dfs1(v[x][i],x);
		dp[x]+=dp[v[x][i]];
	}
	return;
}
void dfs2 (int x,int dep,int mdep,int nwv) {
	if (dp[x]==nw) {mdep=f[x];}
	else {nwv&=a[f[x]];}
	if (dp[x]==0) {gt(nwv&a[x],mdep);}
	int len=v[x].size();
	for (int i=0;i<len;i++) {
		if (v[x][i]==f[x]) {continue;}
		dfs2(v[x][i],dep+1,mdep,nwv);
	}
	return;
}
int main () {
	ex[0]=1;
	for (int i=1;i<P;i++) {
		ex[i]=(1ll*ex[i-1]*10)%P;
		lg[ex[i]]=i;
	}
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		ans=(ans+calc(a[i]))%P;
	}
	for (int i=1;i<=n-1;i++) {
		scanf("%d%d",&x,&y);
		v[x].push_back(y),v[y].push_back(x);
	}
	for (int i=1;i<=n;i++) {
		if (v[i].size()==1) {lf[++cnt]=i;}
	}
	for (int i=1;i<=cnt;i++) {
		for (int j=0;j<30;j++) {las[0][j]=make_pair(0,j);}
		dfs1(lf[i],0);
		dfs2(lf[i],1,0,(1<<30)-1);
		b[lf[i]]=1,nw++;
		//cout << i << "  " << lf[i] << "  " << ans << endl;
	}
	printf("%d\n",ans);
	return 0;
}