Roads Improvement#10684

Roads Improvement (Editorial)

Let $f (v)$ denote the number of ways to improve the quality of roads for the subtree rooted at vertex $v$ . Let $t o$ represent a child of vertex $v$ .

If the road $(v, t o)$ (v, to) remains in bad condition, then all roads in the subtree rooted at vertex $t o$ must be improved.
If the road $(v, t o)$ (v, to) is improved, then the number of ways to improve the roads for the subtree rooted at vertex $t o$ is equal to $f (t o)$ .

Let $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k be the children of $v$ . Then

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot ... \cdot (f (t o_{k}) + 1)

f(v) = (f(to_1) + 1) \cdot (f(to_2) + 1) \cdot ... \cdot (f(to_k) + 1)

If $v$ is a leaf (a vertex with no children), then let $f (v) = 1$ f(v) = 1.

Example

Consider the examples provided in the problem statement. For each vertex $v$ , we'll record the value of $f (v)$ .

In the first example, there are $4$ ways to improve the quality of roads such that on the path from city 1 to any other city, there is no more than one bad road. Bad roads are represented by dashed lines, while improved roads are represented by solid lines.

Algorithm implementation

All calculations are performed modulo $M O D = 1 0^{9} + 7$ MOD = 10^9 + 7.

#define MOD 1000000007

The dfs function computes the value of $f (v)$ — the number of ways to improve the quality of roads for the subtree rooted at vertex $v$ . The parent of $v$ is vertex $p$ .

long long dfs(int v, int p = -1)
{
  long long s = 1;

If $t o_{1}, t o_{2}, ..., t o_{k}$ to_1, to_2, ..., to_k are the children of $v$ , then

f (v) = (f (t o_{1}) + 1) \cdot (f (t o_{2}) + 1) \cdot ... \cdot (f (t o_{k}) + 1)

f(v) = (f(to_1) + 1) \cdot (f(to_2) + 1) \cdot ... \cdot (f(to_k) + 1)

  for (int to : g[v])
    if (to != p)
    {
      long long sub = dfs(to, v);
      s = (s * (sub + 1)) % MOD;
    }
  return s;
}

C++

Read the input data. Construct a tree.

scanf("%d", &n);
g.resize(n + 1);
for (i = 2; i <= n; i++)
{
  scanf("%d", &p);
  g[i].push_back(p);
  g[p].push_back(i);
}

C++

Compute and print the result.

res = dfs(1);
printf("%lld\n", res);