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/(n1) 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/(n1). 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 P.S. Нашёл баг, изза которого был WA: если вы в Pascal пишите z:=n*(n1), где zint64, nlongint, то результат z будет типом longint; правильно так: z:=n; z:=z*(n1). И ещё: лучше выводить не 4 знака в ответе, а все. Edited by author 03.08.2016 11:44 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..? 7 1 2 1 2 3 1 3 5 1 2 4 1 1 6 1 6 7 1 2.3810 I try to solve this problem as "offline LCA problem" with recursive DFS, but I have TLE? Where is mistake? Maybe if you solved LCA problem effective you can get AC, but there is easier way to solve this problem. Resolved Edited by author 12.02.2014 21:04 #pragma comment(linker,"/STACK:1000000000,1000000000") Or use #pragma comment(linker, "/STACK:16777216") Please help me? why I have wa??? Because your solution is wrong! Probably arithmetic overflow or stack overflow. But why crash (stack_overflow)? My program shouldn't use so much memory! [code deleted] Edited by moderator 11.07.2006 23:07 You should manage your stack manually. if n = 1 > res/(n1) = res / 0?????????? No, from condition 2 <= N <= 50000 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. By the way, I have submitted my program many times, and tried to crash it many times. I realised that test #17 has N = 50000, too. And my program use not more than 0.3 sec to pass it. Why do I get TLE at test #23? Please help me, thx in advance. Edited by author 15.09.2010 12:04 I have found the problem. The QuickSort procedure in my problem works quite slow in the OJ. I don't know why. First #23 then #25. At last, I use a random method in the QuickSort and get AC, only 0.078 sec. BTW, this is the first time I got stuck in QuickSort in TIMUS. Congratulations... > The QuickSort procedure in my problem works quite slow in the OJ. I don't know why. It's not the matter of OJ environment but the matter of corner cases. Note that asymptotic complexity of QuickSort in worst case is O(n*n). i dont use quicksort and use one bfs only, why my program have 0.265 s, in time??? 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). Memory limit is 64 Mb now, all recent submits are rejudged. 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. using dfs but own stack management My algo is normal recursion, and I have used pointer, too. It got AC in 0.093sec. Maybe I change the pro into unrecursion and unpointer,it could faster... Can anybode tell how to solve this problem? I had TLE #13 and I don't know what to do!!! I find LCA with own stack! Why I have TLE? What precision should we use in output? Could I have WA#17 because of it? Is double (long double) enough for us? with a precision of 4 decimal digits. double is always enough for calculatings on Timus. Then it (4 digits) should be written in russian statement. To avoid precision problems it is possible to use only integer numbers in solving this task, but I have the same WA#17. Do you use int64? Check it. (50 000 * 50 000 = 2 500 000 000) Yes, of cause, I use unsigned __int64. I tried double, __in64 and long double and still WA17. That must be some other bug... Maybe problem with the following code: for ( i = 1; i <= m_N; ++i ) for ( j = 1; j <= m_N; ++j ) sum += t[ i ][ j ]; sum /= N * (N  1); It must be obviously changed to ... for ( i = 1; i <= m_N; ++i ) for ( j = 1; j <= m_N; ++j ) sum += t[ i ][ j ]) / ( N * (N  1)); overflow ... Maybe it will be usefull : ) And again I've tried both variants... Still WA17 Why both variants! First fragment implyies WA ( it`s obvious ) Did you convert N to __int64 ? It was noted that N*N > signed int. Hmmm ... Send me your code ( see email in my profile ) Yes. The bug what in these data types. I think I should love __int64 from this task and further. Thank you very much! I got AC. I used __int64 (signed) to get total sum of all paths. Then I casted it to double before division by n*(n1)/2. Got WA41. That happened because 'n' was 'int' and that multiplication overflowed. Then I casted 'n' to 'int64' inside that multiplication and got AC. 
