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.
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.
For each query, print a single line containing one integer Fu⋅Fv modulo 232.
1≤wi≤109 for each valid i
in each query, u and v have the same depth
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
5 4 3 2 1
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.
I=inputmod=2**32n,q=map(int, I().split())w=list(map(int, I().split()))tree=dict()vertex=[0 for i in range(n)]vertex=-1for _ in range(n-1):i,j =map(int, I().split())# j,i=max(i,j),min(i,j)vertex[j-1]=i-1for i in range(n):t=vertex[i]aa=[w[i]]while t!=-1:aa.append(w[t])t=vertex[t]tree[i+1]=aafor i in range(q):u,v=map(int, I().split())fu=tree[u]fv=tree[v]ans=0for j in range(len(fu)):ans+=(fu[j]*fv[j])%modprint(ans%mod)
Chegg FREE Premium Accounts:
Udemy Leak Courses:
November Challenge 2020 SOLUTION CodeChef
- Selecting Edges SOLUTION SELEDGE
- Panic! at the Disco SOLUTION PANIC
- Restore Sequence SOLUTION RESTORE
October Lunchtime 2020 CodeChef SOLUTIONS