Can be solved using two DFS calls and tree rerooting in O(N) while maintaining a DP array where DP[node] = sum for all paths from node to all the nodes in its subtree (considering 1 as the initial root). Tree rerooting can be used to calculate the sum for all nodes.

I try to solve this problem as "offline LCA problem" with recursive DFS, but I have TLE? Where is mistake?

P.S. Нашёл баг, из-за которого был WA: если вы в Pascal пишите z:=n*(n-1), где z-int64, n-longint, то результат z будет типом longint; правильно так: z:=n; z:=z*(n-1).
И ещё: лучше выводить не 4 знака в ответе, а все.

Edited by author 03.08.2016 11:44

Let unsigned long long total_cost=0.
For every edge E in tree total_cost +=cost_of_all_paths_lies_on_edge(E).
double ans=2.0*total_cost/n/(n-1) is overflow and and WA#19.
================
Let double ans = 0.
For every edge E in tree ans+=2.0*cost_of_all_paths_lies_on_edge(E)/n/(n-1).
That is AC.
===========
Maybe if not multiply by two in the first scenario there is also AC,  I have not tested.

Don't forget about cargo delivery time:
4
1 2 1
2 3 10
2 4 1
------
6

Edited by author 11.02.2017 17:10

Can you give me the answers for:
-------------------------------------
3
1 2 1
2 3 1
--------------------------------------
6
1 2 1
2 3 1
2 5 1
3 4 1
3 6 1
-------------------------------------
Can you give plz some more test data..?

Кто решил,напишите пару тестов.

Resolved

Edited by author 12.02.2014 21:04

#pragma comment(linker,"/STACK:1000000000,1000000000")

Please help me? why I have wa???

I have run my program on my own conputer (which is slower than the server) several times on the data N = 50000. It takes not more than 0.1 seconds every time.

My algo is DP with the Time Complexity O(N).
To make my program robust, I use QuickSort to sort the edges, and this might use O(N log N) time.

I don't know why I get TLE. Maybe there are some tricks?

Thanks in advance.

out.println(answer);
- output with maximal possible accuracy - WA24
out.printf("%.4f", answer);
- output with exactly 4 digits after decimal point - AC.

By the way, AC source 2369154 (3 Dec 2008) used println. Since then only Java 5->Java 6 changed. And maybe checker.

So is this behaviour bug of println or checker?

Is is possible to change memory limit for this problem from 16 Mb to 32 Mb?

Problem is that 16 Mb is very uncomfortable for Java (and maybe C#) solutions. It is not enough for natural data structure (each vertex and each edge is separate object, each vertex has list of adjacent edges).

In statement 1 <= n.

There is no test where n = 1. And it is impossible because then according to formula in statement answer would be 0/0.

Please update statement - change limitations to 2 <= n.

My algo is O(N) and it works 0.265 s... But there are solutions which work 0.06!! How? Can anybody tell me such algo.

I find LCA with own stack! Why I have TLE?