Scalar Product Tree SOLUTION SCALSUM

Scalar Product Tree November Challenge 2020

Chef has a tree with N vertices (numbered 1 through N). The tree is rooted at the vertex 1. For each valid i, the weight of the i-th vertex is wi.
For a vertex u with depth d (the root has depth 1), let’s denote the sequence of vertices on the path from u to the root by (v1,v2,…,vd), where v1=u and vd=1. Then, let Fu be the vector (i.e. sequence) (wv1,wv2,…,wvd), where the i-th element is Fu,i=wvi for each valid i.
For any two vertices u and v with the same depth d, let’s define the dot product Fu⋅Fv=∑di=1Fu,i⋅Fv,i.
Your task is to answer Q queries. In each query, you are given two vertices u and v with the same depth, and you should find Fu⋅Fv. Since the dot product can be large, compute it modulo 232.
Input
The first line of the input contains two space-separated integers N and Q.
The second line contains N space-separated integers w1,w2,…,wN.
Each of the next N−1 lines contains two space-separated integers u and v denoting that vertices u and v are connected by an edge.
Q lines follow. Each of these lines contains two space-separated integers u and v describing a query.
Output
For each query, print a single line containing one integer Fu⋅Fv modulo 232.
Constraints
1≤N,Q≤3⋅105
1≤wi≤109 for each valid i
1≤u,v≤N
in each query, u and v have the same depth
Subtasks
Subtask #1 (15 points, time limit 1 second): N,Q≤1,000
Subtask #2 (45 points, time limit 2 seconds): N,Q≤105
Subtask #3 (40 points, time limit 3.5 seconds): original constraints
Example Input
5 2
5 4 3 2 1
1 2
1 3
2 4
2 5
2 3
4 5
Example Output
37
43
Explanation
In the first query, F2=(4,5) and F3=(3,5), so the scalar product is 4⋅3+5⋅5=37.
In the second query, F4=(2,4,5) and F5=(1,4,5), so the scalar product is 2⋅1+4⋅4+5⋅5=43.
 
SOLUTION :
I=input
mod=2**32
n,q=map(int, I().split())
w=list(map(int, I().split()))
tree=dict()
vertex=[0 for i in range(n)]
vertex[0]=-1
for _ in range(n-1):
    i,j =map(int, I().split())  
    # j,i=max(i,j),min(i,j)
    vertex[j-1]=i-1
for i in range(n):
    t=vertex[i]
    aa=[w[i]]
    while t!=-1:
        aa.append(w[t])
        t=vertex[t]
    tree[i+1]=aa
for i in range(q):
    u,v=map(int, I().split())
    fu=tree[u]
    fv=tree[v]
    ans=0
    for j in range(len(fu)):
        ans+=(fu[j]*fv[j])%mod
    print(ans%mod)
 

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment