66 lines
1.1 KiB
Java
66 lines
1.1 KiB
Java
package chelper;
|
|
|
|
import java.util.ArrayList;
|
|
import java.util.HashSet;
|
|
import java.util.List;
|
|
import java.util.Set;
|
|
|
|
import io.InputReader;
|
|
import io.OutputWriter;
|
|
import misc.SimpleSavingChelperSolution;
|
|
|
|
|
|
public class B extends SimpleSavingChelperSolution {
|
|
|
|
public void solve(int testNumber, InputReader in, OutputWriter out) {
|
|
wrapSolve(testNumber, in, out);
|
|
}
|
|
|
|
int n;
|
|
List<List<Integer>> edges;
|
|
long c1 = 0;
|
|
long c2 = 0;
|
|
Set<Integer> visited;
|
|
|
|
@Override
|
|
public void solve(int testNumber) {
|
|
n = in.nextInt();
|
|
|
|
edges = new ArrayList<>();
|
|
for (int i = 0; i < n; i++) {
|
|
edges.add(new ArrayList<>());
|
|
}
|
|
|
|
|
|
for (int i = 0; i < n - 1; i++) {
|
|
int a = in.nextInt() - 1;
|
|
int b = in.nextInt() - 1;
|
|
|
|
edges.get(a).add(b);
|
|
edges.get(b).add(a);
|
|
}
|
|
|
|
visited = new HashSet<>();
|
|
dfs(0, true);
|
|
|
|
long total = c1 * c2 - (n - 1);
|
|
out.println(total);
|
|
}
|
|
|
|
void dfs(int v, boolean color) {
|
|
visited.add(v);
|
|
if (color) {
|
|
c1++;
|
|
} else {
|
|
c2++;
|
|
}
|
|
|
|
for (Integer o : edges.get(v)) {
|
|
if (visited.contains(o)) {
|
|
continue;
|
|
}
|
|
dfs(o, !color);
|
|
}
|
|
}
|
|
}
|