XR-3 E Namid[A]me 题解
ix35
·
·
题解
全文链接：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。
**题目解法：**
显然树中的任意一条路径是以某个叶子为根时的一段祖先链，我们不妨依次枚举叶子 $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)$。
```cpp
#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;
}
```