All submissions for this problem are available.
Everybody knows that there are a lot of complicated problems on CodeChef and it’s quite difficult to solve them. However, very few people know that testing these problems is much more elaborate process than solving. Hosting Chef’s great contests would be impossible without his testers - Anton and Hiroto. The number of problems they solved and tested probably won’t fit in 32-bit integer. These guys do very big amount of work and of course they also need to have a rest. They are having vacation for the next ten days. Of course, they’ve chosen ChefLand as a place to go.
There are N cities in ChefLand and every city is denoted by its integer number. Surprisingly these numbers are not to be distinct. Anton is fond of Math so he quickly counted the sum of squares of all positive integer divisors for every this number; let’s call this sum for number that denotes ith city S(i). Hiroto considers city i to be beautiful if S(i) is odd, otherwise it is ugly for him.
It’s important to mention that the cities of ChefLand are connected by bidirectional roads. It took Hiroto a couple of seconds to notice that there are exactly N-1 roads and that it’s possible to reach every city from every other city by existing roads.
Our testers want their vacation to consist of interesting trips. Formally trip is a path between two cities (Anton swears that there is an unique path between each pair of cities, so let’s trust him:)); the length of the trip is a number of cities it consists of. Furthermore, visiting of a single city is also a trip of length 1. The time of having any trip is equal to its length. Hiroto considers a trip to be interesting if the number of beautiful cities in it is not less than the number of ugly cities.
Anton and Hiroto want to try every interesting trip. Since our testers are very smart and provident, they want to know the exact time it will take them to go through all the interesting trips. Note that if they had a trip from A to B then they are not interested in having trip from B to A.
The first line contains single integer N – the number of cities in ChefLand. Then N-1 lines follow – description of the roads. Each road is described by a pair of integers in [1, N] range. Then you are given N numbers in the next line. Ith of them is the number that denotes city i.
The first and only line of the output should contain the total length of all the interesting trips.
1 ≤ N ≤ 300000 (3*105)
1 ≤ Number that denotes any city ≤ 1500000 (1.5*106)
Input: 3 1 2 1 3 3 1 1 Output: 9
ExplanationHere we have S(2)=S(3)=1 and S(1)=10 (1 + 32), so the first city is ugly and other two are beautiful. (2, 2) – 1 (3, 3) – 1 (1, 2) – 2 (1, 3) – 2 (2, 3) – 3 1+1+2+2+3=9 The (1, 1) trip is not interesting.
|Tags||Rubanenko, feb13, hard, tree|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.