Regular Forestation (Problem F, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Jonathan Mulaywan Woenardi

# Problem Statement

A forestation is an act of planting a bunch of trees to grow a forest, usually to replace a forest that had been cut down. Strangely enough, graph theorists have another idea on how to make a forest, i.e. by cutting down a tree!

A tree is a graph of $N$ nodes connected by $N - 1$ edges. Let $u$ be a node in a tree $U$ which degree is at least 2 (i.e. directly connected to at least 2 other nodes in $U$). If we remove $u$ from $U$, then we will get two or more disconnected (smaller) trees, or also known as forest by graph theorists. In this problem, we are going to investigate a special forestation of a tree done by graph theorists.

Let $V(S)$ be the set of nodes in a tree $S$ and $V(T)$ be the set of nodes in a tree $T$. Tree $S$ and tree $T$ are identical if there exists a bijection $f : V(S) \rightarrow V(T)$ such that for all pairs of nodes $(s_i, s_j)$ in $V(S)$, $s_i$ and $s_j$ is connected by an edge in $S$ if and only if node $f(s_i)$ and $f(s_j)$ is connected by an edge in $T$. Note that $f(s) = t$ implies node $s$ in $S$ corresponds to node $t$ in $T$.

We call a node $u$ in a tree $U$ as a good cutting point if and only if the removal of $u$ from $U$ causes two or more disconnected trees, and all those disconnected trees are pairwise identical.

Given a tree $U$, your task is to determine whether there exists a good cutting point in $U$. If there is such a node, then you should output the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point.

For example, consider the following tree of 13 nodes.

![IMAGE](icpc-jakarta-2019-forest-1.png)

There is exactly one good cutting point in this tree, i.e. node 4. Observe that by removing node 4, we will get three identical trees (in this case, line graphs), i.e. $\{5, 1, 7, 13\}$, $\{8, 2, 11, 6\}$, and $\{3, 12, 9, 10\}$, which are denoted by $A$, $B$, and $C$ respectively in the figure.

- The bijection function between $A$ and $B$: $f(5) = 8$, $f(1) = 2$, $f(7) = 11$, and $f(13) = 6$.
- The bijection function between $A$ and $C$: $f(5) = 3$, $f(1) = 12$, $f(7) = 9$, and $f(13) = 10$.
- The bijection function between $B$ and $C$: $f(8) = 3$, $f(2) = 12$, $f(11) = 9$, and $f(6) = 10$.

Of course, there exists other bijection functions for those trees.

# Input

Input begins with a line containing an integer: $N$ $(3 \leq N \leq 4000)$ representing the number of nodes in the given tree. The next $N - 1$ lines each contains two integers: $a_i\ b_i$ $(1 \leq a_i < b_i \leq N)$ representing an edge $(a_i, b_i)$ in the given tree. It is guaranteed that any two nodes in the given tree are connected to each other by a sequence of edges.

# Output

Output in a line an integer representing the maximum number of disconnected trees that can be obtained by removing exactly one good cutting point, or output $-1$ if there is no such good cutting point.

# Sample Input #1
```
13
1 5
1 7
2 4
2 8
2 11
3 12
4 7
4 12
6 11
7 13
9 10
9 12
```
# Sample Output #1
```
3
```
# Explanation for the sample input/output #1

This is the example from the problem description.

# Sample Input #2
```
6
1 2
1 3
2 4
3 5
3 6
```

# Sample Output #2
```
-1
```

Sample inputs:
13
1 5
1 7
2 4
2 8
2 11
3 12
4 7
4 12
6 11
7 13
9 10
9 12

6
1 2
1 3
2 4
3 5
3 6

Sample outputs:
3

-1

# Solution Analysis
Analysis author: Jonathan Mulaywan Woenardi

The *centroid* of a tree is a node whose removal causes the remaining tree(s) to have at most half the number of nodes of the original tree. A tree can only have at most $2$ centroids.

Recall that removal of a good cutting point (as defined in the problem statement) will cause at least two identical disconnected trees. Observe that each of those disconnected trees cannot have more than half the number of nodes of the original tree. Therefore, if a good cutting point exists in the given tree, then it must be at the centroid of the tree.

Tree centroid can be found in $O(N)$—alternatively, an $O(N \log N)$ or $O(N^2)$ if implemented efficiently, can also be used as $N$ in this problem is quite small.

The remaining task is to check whether the disconnected trees are identical (also called *isomorphic*). Rooted tree isomorphism can be solved in $O(N)$ with parenthetical tuples (AHU algorithm), although an easier $O(N^2)$ version suffices. For this problem where the trees are unrooted, simply use the centroid of each tree as the root. You need to be careful when the tree has $2$ centroids. If you opt to test all nodes in each tree as the root for tree isomorphism, then you will need the $O(N)$ algorithm to do the tree isomorphism.

Note that using the *center* of a tree (as opposed to centroid) as the only candidate for the good cutting point will not work (**WRONG-ANSWER**). The center of a tree is a node that has the lowest eccentricity (or lies in the diameter path of a tree).

Special judge (C++ scorer):
/**
 * Default validator from https://github.com/Kattis/problemtools
 * Modified (as small as possible) to Judgels format by jonathanirvings.
 */

#include <fstream>
#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <cstdarg>

std::ifstream judgein, judgeans, conans;
FILE *judgemessage = NULL;
FILE *diffpos = NULL;
int judgeans_pos, con_pos;
int judgeans_line, con_line;

void ac() {
  puts("AC");
  exit(0); 
}

void wa() {
  puts("WA");
  exit(0);
}

void wrong_answer(const char *err, ...) {
  wa();
}

void judge_error(const char *err, ...) {
  va_list pvar;
  va_start(pvar, err);
  // If judgemessage hasn't been set up yet, write error to stderr
  if (!judgemessage) judgemessage = stderr;
  vfprintf(judgemessage, err, pvar);
  fprintf(judgemessage, "\n");
  assert(!"Judge Error");
}

bool isfloat(const char *s, double &val) {
  char trash[20];
  double v;
  if (sscanf(s, "%lf%10s", &v, trash) != 1) return false;
  val = v;
  return true;
}

template <typename Stream>
void openfile(Stream &stream, const char *file, const char *whoami) {
  stream.open(file);
  if (stream.fail()) {
    judge_error("%s: failed to open %s\n", whoami, file);
  }
}

FILE *openfeedback(const char *feedbackdir, const char *feedback, const char *whoami) {
  std::string path = std::string(feedbackdir) + "/" + std::string(feedback);
  FILE *res = fopen(path.c_str(), "w");
  if (!res) {
    judge_error("%s: failed to open %s for writing", whoami, path.c_str());
  }
  return res;
}

const char *USAGE = "Usage: %s judge_in judge_ans contestant_ans";

int main(int argc, char **argv) {
  if(argc < 4) {
    judge_error(USAGE, argv[0]);
  }
  openfile(judgein, argv[1], argv[0]);
  openfile(judgeans, argv[2], argv[0]);
  openfile(conans, argv[3], argv[0]);

  bool case_sensitive = false;
  bool space_change_sensitive = false;
  bool use_floats = false;
  double float_abs_tol = -1;
  double float_rel_tol = -1;

  for (int a = 4; a < argc; ++a) {
    if        (!strcmp(argv[a], "case_sensitive")) {
      case_sensitive = true;
    } else if (!strcmp(argv[a], "space_change_sensitive")) {
      space_change_sensitive = true;
    } else if (!strcmp(argv[a], "float_absolute_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_abs_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_relative_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      ++a;
    } else if (!strcmp(argv[a], "float_tolerance")) {
      if (a+1 == argc || !isfloat(argv[a+1], float_rel_tol))
        judge_error(USAGE, argv[0]);
      float_abs_tol = float_rel_tol;
      ++a;
    } else {
      judge_error(USAGE, argv[0]);
    }
  }
  use_floats = float_abs_tol >= 0 || float_rel_tol >= 0;

  judgeans_pos = con_pos;
  judgeans_line = con_line = 1;
   
  std::string judge, team;
  char trash[20];
  while (true) {
    // Space!  Can't live with it, can't live without it...
    while (isspace(judgeans.peek())) {
      char c = (char)judgeans.get();
      if (space_change_sensitive) {
        int d = conans.get();
        if (c != d) {
          wrong_answer("Space change error: got %d expected %d", d, c);
        }
        if (d == '\n') ++con_line;
        ++con_pos;
      }
      if (c == '\n') ++judgeans_line;
      ++judgeans_pos;
    }
    while (isspace(conans.peek())) {
      char d = (char)conans.get();
      if (space_change_sensitive) {
        wrong_answer("Space change error: judge out of space, got %d from team", d);
      }
      if (d == '\n') ++con_line;
      ++con_pos;
    }

    if (!(judgeans >> judge))
      break;

    if (!(conans >> team)) {
      wrong_answer("User EOF while judge had more output\n(Next judge token: %s)", judge.c_str());
    }
     
    double jval, tval;
    if (use_floats && isfloat(judge.c_str(), jval)) {
      if (!isfloat(team.c_str(), tval)) {
        wrong_answer("Expected float, got: %s", team.c_str());
      }
      if(!(fabs(jval - tval) <= float_abs_tol) && 
         !(fabs(jval - tval) <= float_rel_tol*fabs(jval))) {
        wrong_answer("Too large difference.\n Judge: %s\n Team: %s\n Difference: %le\n (abs tol %le rel tol %le)", 
               judge.c_str(), team.c_str(), jval-tval, float_abs_tol, float_rel_tol);
      }
    } else if (case_sensitive) {
      if (strcmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    } else {
      if(strcasecmp(judge.c_str(), team.c_str()) != 0) {
        wrong_answer("String tokens mismatch\nJudge: \"%s\"\nTeam: \"%s\"", judge.c_str(), team.c_str());
      }
    }
    judgeans_pos += judge.length();
    con_pos += team.length();
  }

  if (conans >> team) {
    wrong_answer("Trailing output:\n%s", team.c_str());
  }

  ac();
}