The main idea of the title
There is one tree with
n
n
A tree of n points, each point has a point weight
a
i
a_i
ai?,
f
(
i
,
j
)
f(i,j)
f(i,j) and
g
(
i
,
j
)
g(i,j)
g(i,j) respectively represent
i
i
i arrive
j
j
Find the weight sum and weight or or on the path of j.
∑
i
=
1
n
∑
j
=
i
n
f
(
i
,
j
)
g
(
i
,
j
)
\sum\limits_{i=1}^n\sum\limits_{j=i}^nf(i,j)^{g(i,j)}
i=1∑n?j=i∑n?f(i,j)g(i,j)
Output answer model
111121
111121
The value after 111121.
To facilitate calculation, define
0
0
=
0
0^0=0
00=0.
n
≤
1
0
5
,
a
i
≤
1
0
9
n\leq 10^5,a_i\leq 10^9
n≤105, ai?≤109, the leaves of the given tree (degree is
1
1
1 point) does not exceed
100
100
100.
Solution
It is not difficult to find that for trees from
i
i
i arrive
j
j
The chain of j, let
k
k
k is a point on the chain, then the essentially different
f
(
i
,
k
)
f(i,k)
f(i,k) does not exceed
log
?
A
\log A
logA, among which
A
A
A is
a
i
a_i
The value range of ai?.
g
(
i
,
k
)
g(i,k)
The same goes for g(i,k).
say
f
(
i
,
j
)
,
g
(
i
,
j
)
f(i,j),g(i,j)
f(i,j),g(i,j) is a number pair, so for the tree from
i
i
i arrive
j
j
The chain of j, let
k
k
k is a point on the chain, then there are essentially different pairs of numbers
O
(
log
?
A
)
O(\log A)
O(logA) pieces.
Remember the number of leaves as
k
k
k, for each point, we use
O
(
k
log
?
A
)
O(k\log A)
O(klogA) maintains the number of pairs from this point to each subtree node (the path to each leaf node has the most
O
(
log
?
A
)
O(\log A)
O(logA) essentially different number pairs), the total time complexity is
O
(
n
k
log
?
A
)
O(nk\log A)
O(nklogA).
For the contribution of a chain hanging on a point, we can think of it as two leaf nodes intersecting above, there will be at most
O
(
k
2
)
O(k^2)
O(k2) merges, each merge is
O
(
log
?
3
A
)
O(\log^3 A)
O(log3A) (to enumerate both sides of this chain, there are a total of
O
(
log
?
2
A
)
O(\log^2 A)
O(log2A) times, we also need to use fast power to find the contribution to the answer, which is
O
(
log
?
A
)
O(\log A)
O(logA)), so the time complexity of this part is
O
(
k
2
log
?
3
A
)
O(k^2\log^3A)
O(k2log3A).
We consider how to save fast power
log
?
A
\log A
logA.
It can be optimized using the power of the speed of light, using
O
(
p
p
)
O(p\sqrt p)
O(pp
p
p
p is the modulus, that is
111121
111121
111121, is a prime number), then it can
O
(
1
)
O(1)
O(1) to find
f
(
i
,
j
)
g
(
i
,
j
)
f(i,j)^{g(i,j)}
f(i,j)g(i,j).
The total time complexity is
O
(
n
k
log
?
A
+
k
2
log
?
2
A
+
p
p
)
O(nk\log A + k^2\log^2A + p\sqrt p)
O(nklogA + k2log2A + pp
code
#include<bits/stdc + + .h>
using namespace std;
const int N=100000,siz=350;
const long long mod=111121;
int n,vl[N + 5];
long long ans=0,pw[mod + 5][siz + 5];
vector<int>g[N + 5];
map<pair<int,int>,int>mp[N + 5];
void init(){<!-- -->
for(int i=1;i<mod;i + + ){<!-- -->
pw[i][0]=1;
for(int j=1;j<=siz;j + + ) pw[i][j]=pw[i][j-1]*i%mod;
}
}
long long mi(long long x,long long y){<!-- -->
x%=mod;y%=mod-1;
return pw[pw[x][siz]][y/siz]*pw[x][y%siz]%mod;
}
void dfs(int u,int fa){<!-- -->
mp[u][{<!-- -->vl[u],vl[u]}]=1;
ans=(ans + mi(vl[u],vl[u]))%mod;
for(int v:g[u]){<!-- -->
if(v==fa) continue;
dfs(v,u);
for(auto a:mp[u]){<!-- -->
for(auto b:mp[v]){<!-- -->
ans=(ans + 1ll*a.second*b.second%mod
*mi(a.first.first &b.first.first,
a.first.second|b.first.second)%mod)%mod;
}
}
for(auto b:mp[v]){<!-- -->
mp[u][{<!-- -->vl[u] & amp;b.first.first,vl[u]|b.first.second}] + =b.second;
}
}
}
int main()
{<!-- -->
// freopen("abstract.in","r",stdin);
// freopen("abstract.out","w",stdout);
init();
scanf("%d", & amp;n);
for(int i=1;i<=n;i + + ){<!-- -->
scanf("%d", & amp;vl[i]);
}
for(int i=1,x,y;i<n;i + + ){<!-- -->
scanf("%d%d", & amp;x, & amp;y);
g[x].push_back(y);g[y].push_back(x);
}
dfs(1,0);
printf("%lld",ans);
return 0;
}