Sum of distances

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There is a directed acyclic graph with N vertices. The vertices are numbered from 1 to N.
For every 1 ≤ i ≤ N1, there is an edge from vertex i to vertex i+1, which has weight a_{i}.
For every 1 ≤ i ≤ N2, there is an edge from vertex i to vertex i+2, which has weight b_{i}.
For every 1 ≤ i ≤ N3, there is an edge from vertex i to vertex i+3, which has weight c_{i}.
There are no other edges.
For each pair of vertices s, t where s < t, let d(s, t) denote the length of the shortest path from s to t. Your task is to compute the sum of d(s, t) for every 1 ≤ s < t ≤ N.
Input
First line of the input contains an integer T denoting number of test cases. T test cases follow.
For each test case:
The first line contains an integer N.
The second line contains N  1 integers a_{1}, a_{2}, ..., a_{N1}.
The third line contains N  2 integers b_{1}, b_{2}, ..., b_{N2}.
The fourth line contains N  3 integers c_{1}, c_{2}, ..., c_{N3}.
Output
For each test case, output a single line containing an integer, denoting the answer. It can be proved that the answer fits in the signed 64bit type.
Constraints
 1 ≤ T ≤ 10^{4}
 4 ≤ N ≤ 10^{5}
 1 ≤ sum of N over all test cases ≤ 3*10^{5}
 1 ≤ a_{i}, b_{i}, c_{i }≤ 10^{4}
Subtasks
Subtask #1 (8 points):
 N ≤ 10^{3}.
 1 ≤ sum of N over all test cases ≤ 10^{4}.
Subtask #2: (13 points):
 b_{i} = a_{i} + a_{i+1}.
 c_{i} = a_{i} + a_{i+1} + a_{i+2}.
Subtask #3: (46 points):
 c_{i} = a_{i} + a_{i+1} + a_{i+2}.
Subtsak #4: (33 points):
 Original constraints.
Example
Input: 2 4 1 1 1 1 1 1 5 1 2 3 4 2 3 4 3 4 Output: 6 31
Explanation
Example case 1. In this test case the distance between the node A and the node B will be equal to one for all pairs (A, B). So for all six pairs we get the distance 1 and the final sum 6.
Author:  r_64 
Tester:  xcwgf666 
Editorial  https://discuss.codechef.com/problems/SUMDIS 
Tags  divideandconq, geometry, graph, hard, march17, r_64 
Date Added:  26012017 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions