Cleaning Robots (Problem B, The 2019 ICPC Asia Jakarta Regional Contest, 2019)
Time limit: 1 sec
Memory limit: 256MB
Author: Suhendry Effendy

# Problem Statement
The new ICPC town has $N$ junctions (numbered from $1$ to $N$) which are connected by $N - 1$ roads. It is possible from one junction to go to any other junctions by going through one or more roads. To make sure all the junctions are well-maintained, the government environment agency is planning to deploy their newest advanced cleaning robots. In addition to its cleaning ability, each robot is also equipped with a movement ability such that it can move from one junction to any other junctions connected by roads. However, as you might have guessed, such robots are not cheap. Therefore, the agency is considering the following deployment plan.

Let $T_k$ be the set of junctions which should be cleaned by the $k^{th}$ robot (also known as, the robot’s task), and $|T_k| \geq 1$ be the number of junctions in $T_k$. The junctions in $T_k$ form a **path**, i.e. there exists a sequence of $v_1, v_2, \ldots, v_{|T_k|}$ where $v_i \in T_k$ and $v_i \ne v_j$ for all $i \ne j$ such that each adjacent junction in this sequence is connected by a road. The union of $T$ for all robots is equal to the set of all junctions in ICPC town. On the other hand, no two robots share a common junction, i.e. $T_i \cap T_j = \emptyset$ if $i \ne j$.

To avoid complaints from citizens for an inefficient operation, the deployment plan should be *irreducible*; in other words, there should be no two robots, $i$ and $j$, such that $T_i \cup T_j$ forms a (longer) path. Note that the agency does not care whether the number of robots being used is minimized as long as all the tasks are irreducible.

Your task in this problem is to count the number of feasible deployment plan given the town’s layout. A plan is feasible if and only if it satisfies all the above-mentioned requirements.

For example, let $N = 6$ and the roads are $\{(1,3), (2,3), (3,4), (4,5), (4,6)\}$. There are $5$ feasible deployment plans as shown in the following figure.

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

- The first plan uses 2 robots (labeled as A and B in the figure) to clean $\{1, 2, 3\}$ and $\{4, 5, 6\}$.
- The second plan uses 3 robots (labeled as A, B, and C in the figure) to clean $\{1, 3, 4, 6\}$, $\{2\}$, and $\{5\}$.
- The third plan uses 3 robots to clean $\{1, 3, 4, 5\}$, $\{2\}$, and $\{6\}$.
- The fourth plan uses 3 robots to clean $\{1\}$, $\{2, 3, 4, 6\}$, and $\{5\}$.
- The fifth plan uses 3 robots to clean $\{1\}$, $\{2, 3, 4, 5\}$, and $\{6\}$.

No other plans are feasible in this case. For example, the plan $\{\{1, 3\}, \{2\}, \{4, 5, 6\}\}$ is not feasible as the task $\{1, 3\}$ and $\{2\}$ can be combined into a longer path $\{1, 3, 2\}$. The plan $\{\{1, 2, 3, 4\}, \{5\}, \{6\}\}$ is also not feasible as $\{1, 2, 3, 4\}$ is not a path.

# Input

Input begins with a line containing an integer: $N$ $(1 \leq N \leq 100\,000)$ representing the number of junctions.  
The next $N - 1$ lines each contains two integers: $u_i\ v_i$ $(1 \leq u_i < v_i \leq N)$ representing a road connecting junction $u_i$ and junction $v_i$. It is guaranteed that it is possible from one junction to go to any other junctions by going through one or more roads.

# Output

Output in a line an integer representing the number of feasible deployment plans. As this output can be large, you need to modulo the output by $1\,000\,000\,007$.


# Sample Input #1
```
6
1 3
2 3
3 4
4 5
4 6
```
# Sample Output #1
```
5
```
# Explanation for the sample input/output #1

This is the example from the problem description.

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

Sample inputs:
6
1 3
2 3
3 4
4 5
4 6

5
1 2
2 3
2 4
4 5

Sample outputs:
5

3

# Solution Analysis
Analysis author: Suhendry Effendy

This problem can be solved with dynamic programming. The following analysis assumes the tree is rooted (simply select an arbitrary node as the root).

First, let us define a state $\langle u, s \rangle$ where $u$ is a node and $s$ is either $\{0, 1, 2\}$ as follows:

- $\langle u, 0 \rangle$ – node $u$ and its parent are cleaned by a different robot.
- $\langle u, 1 \rangle$ – node $u$ and its parent are cleaned by a different robot, and node $u$ should be cleaned together with its $2$ direct children.
- $\langle u, 2 \rangle$ – node $u$ and its parent are cleaned by the same robot.

Let a function $f(u, s)$ be the number of feasible deployment plans on a subtree rooted at node $u$. Then, the solution to this problem is simply $f(root, 0)$.

With these state and function definitions, we can derive the recurrence relation between states. Let $\eta^u$ be the set of node $u$’s children, $\eta^u_i$ be the $i^{th}$ child of node $u$, and $n$ be the number of node $u$’s children (i.e. $|\eta^u|$). The recurrence relation is:

$$
f(u, s) =
\begin{cases}
h_1(u,1) + h_2(u) + h_3(u) & \text{if } s = 0, \\
h_2(u) & \text{if } s = 1, \\
h_1(u,0) + h_3(u) & \text{if } s = 2
\end{cases}
$$

$$
h_1(u, s) = \sum_{i = [1..n]} \prod_{v \in \eta_u}
\begin{cases}
f(v, 2) & \text{if } v = \eta^u_i \\
f(v, s) & \text{if } v \ne \eta^u_i
\end{cases}
$$

$$
h_2(u) = \sum_{i = [1..n]} \sum_{j = (i..n)} \prod_{v \in \eta_u}
\begin{cases}
f(v, 2) & \text{if } v = \eta^u_i \text{ or } v = \eta^u_j \\
f(v, 0) & \text{if } v \ne \eta^u_i \text{ and } v \ne \eta^u_j
\end{cases}
$$

$$
h_3(u) = \prod_{v \in \eta_u} f(v, 1)
$$


The function $h_1(u, s)$ handles the case where we should choose one child to be cleaned together with node $u$ while the remaining other children are in state $\langle \eta^u_i, s \rangle$. The function $h_2(u)$ handles the case where we should choose two children to be cleaned together with node $u$ while the remaining other children are in state $\langle \eta^u_i, 0 \rangle$. The function $h_3(u)$ handles the case where node $u$ is not cleaned together with any of its children.



Observe that the time complexity to compute $h_1(u, s)$ naively is $O(n^2)$, while $h_2(u)$ is $O(n^3)$, and $h_3(u)$ is $O(n)$. Therefore, the time complexity to compute the above recurrence relation is $O(N^3)$, which is too slow for this problem with $N \leq 100\,000$. Optimizing these functions is the real challenge for this problem.



**First good news:** The function $h_1(u, s)$ can be computed in $O(n)$.

$$
h_1(u, s) = \prod_{v \in \eta_u} f(v, s) \times \sum_{v \in \eta_u} f(v, 2) f^{-1}(v, s)
$$

Note that we need to use the multiplicative modular inverse to compute $\frac{1}{f(v, s)}$ as we only need to find the modulo while the full number can be very large.

Another good news: The function $h_2(u)$ can be computed in $O(n)$.

$$
x^u_i = f(\eta^u_i, 2) f^{-1}(\eta^u_i, 0)
$$

$$
y^u_i = \sum_{j = [i..n]} x^u_j
$$

$$
h_2(u) = \prod_{v \in \eta_u} f(v, 0) \times \sum_{i = [1..n]} x^u_i y^u_{i+1}
$$


Note that $y^u_i$ can be computed in $O(n)$ for all $i$ with partial sum technique, making it $O(1)$ for each $i$. Also note that $y^u_i = 0$ if $i > n$. The original $h_2(u)$ function is actually in the form of $a_1 a_2 b_3 b_4 b_5 + a_1 b_2 a_3 b_4 b_5 + a_1 b_2 b_3 a_4 b_5 + \cdots + b_1 b_2 a_3 b_4 a_5 + b_1 b_2 b_3 a_4 a_5$ (an example where $n = 5$), i.e. there are 2 functions, $a$ and $b$, choose two indexes to have $a$ while the remainings are $b$; evaluate each combination (perform the multiplications) and sum the results for all the possible combinations. There are $\binom{n}{2}$ combinations, and evaluating one combination is $O(n)$, thus, the original time complexity is $O(n^3)$. Try to optimize this summation into $O(n)$ and you will arrive at the above equations.


We do not need to optimize the function $h_3(u)$ as it is already in $O(n)$. All seems good! The solution now becomes $O(N)$. However, there is a caveat in the implementation: Beware when you want to compute the modular multiplicative inverse of zero (there is no such thing). You’ll need to further work on the equations on such a case. 

**Hint:** We only need to consider the cases when there is at most $1$ zero for $h_1(u)$ and $2$ zeros for $h_2(u)$.


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();
}