DIV1 2nd:

Root the tree at 1. Find the following for each node using dfs:
cost[i] = cost of node i as described in the problem statement.
subcost[i] = sum of cost[j] across every node j which lies in the subtree of i.
sm[i] = sum of values nodes on the path from 1 to node i.
subsum[i]= sum of sm[j] across every node j which lies in the subtree of i.
ct[i]= number of nodes in the subtree of i.

Now if we root the tree at a child X of 1 instead, the difference in the sum of costs will be as follows:
A. For every node j in the subtree of X, node 1 will no longer lie on the paths and the coefficient of terms of cost will decrease by 1, effectively the new cost will be:
cost[j]=cost[j]-sm[j]-val[1]
The effective change in subcost will be:
subcost[i]=subcost[i]-subsum[i]-ct[i]*val[1]
B. For every node j outside the sub tree of X, node X will also lie on the paths and the coefficient of terms of cost will increase by 1, effectively the new cost will be:
cost[j]=cost[j]+sm[j]+val[X]
We can calculate the change similar to the previous step.
After calculation for total cost rooting the node in every possible way, we choose the minimum.
Time Complexity: O(N)


DIV1 3rd:
We can find :
sum{for all possible combination(x1,x2..xn)}(product{i=1 to n}(A[i]+xi)) ---------(1)
and then divide it by (M+N-1)C(N-1).

Lets consider a polynomial,
P(x,i) = sum{i=0 to inf}((A[i]+i)*x^i)

We can see that (1) is coefficient of x^m in product{i=1 to n}P(x,i)

If we try to compute this directly using ntt, the time complexity would by NMlogM

Lets see P(x,i):
P(x,i) = sum{i=0 to inf}(A[i]*x^i + i*x^i)
P(x,i) = (A[i]*sum{i=0 to inf}x^i) + (sum{i=0 to inf}i*x^i) ----------------(2)
Now sum{i=0 to inf}x^i is expansion of 1/(1-x)

And sum{i=0 to inf}i*x^i,
we know 1/(1-x) = 1+x+x^2...
Differentiating and multiplying by x,we get
x/(1-x)^2 = x+2x+3x^2...=sum{i=0 to inf}i*x^i

So resubstituting these in (2), we get
P(x,i) = (A[i]/(1-x))+(x/(1-x)^2)
P(x,i)=(x*(1-A[i])+A[i])/(1-x)^2

So now since degree of numerator is 1, we can multiply using divide and conquer and ntt in O(MlogN*logM)

Now we have something like this:

(1) = (polynomial of degree atmost m)*(1-x)^(-2n)

We can expand (1-x)^-2n and then iterating the power of x in (1-x)^-2n we can calculate coefficient of x^m.

Time Complexity: O(MlogNlogM)