•Article•3 months ago

Trees

Trees are one of the key data structures in algorithms and appear in a wide range of problems.

A tree is a connected, acyclic, undirected graph.

A graph $G = (V, E)$ is called a tree if it satisfies the following properties:

Connected — there is a path between every pair of vertices in the graph.
Acyclic — the graph contains no cycles.

In a tree with $n$ vertices, there are always exactly $n - 1$ edges.

Fundamental Properties of a Tree

1. Connectivity and Uniqueness of Paths

In a tree, there is a unique path between any pair of vertices.

2. Number of Edges

For any tree:

∣ E ∣ = ∣ V ∣ - 1

3. No Cycles

Adding even a single edge to a tree always creates a cycle.

4. Root (for a rooted tree)

If one vertex is chosen as the root, the tree becomes directed from the root to its descendants. This is used in recursive traversals and algorithms ( $D FS$ , $L C A$ , etc.).

5. Subtrees

Any vertex along with its descendants forms a subtree. A subtree is itself a tree.

6. Leaves

Vertices with zero children (in a rooted tree) are called leaves.

7. Depth and Height

Depth of a vertex is the distance from the root to that vertex.
Height of a tree is the maximum depth among all vertices.

8. Center of a Tree

The center is the vertex (or a pair of adjacent vertices) that minimizes the maximum distance to all other vertices.

Alternative Definitions of a Tree

The following definitions of a tree are equivalent and can be used in different contexts:

A cycle-free graph that becomes disconnected if any edge is removed.
A connected graph with $n$ vertices and $n - 1$ edges.
An acyclic graph with $n - 1$ edges and exactly one connected component.

Representing Trees in Code

Depending on the problem and the type of tree (general, binary, rooted, etc.), different data structures are used:

1. Adjacency Lists

This approach is often used in competitive programming problems and when working with undirected or directed trees.

int n;
vector<vector<int>> tree(n); // tree with n vertices

// adding an edge between vertices u and v
tree[u].push_back(v);
tree[v].push_back(u); // for an undirected tree

2. Parent Array

A very compact representation, especially useful when the tree is already constructed.

vector<int> parent(n); // parent[i] --- he parent of vertex i
// if i is the root, parent[i] is usually set to -1 or 0

3. Pointers / Structures (OOP Style)

Commonly used when constructing binary trees, tries, decorators, especially in Python/Java/C++ with object-oriented programming.

Binary Tree:

struct Node 
{
  int val;
  Node* left;
  Node* right;
  Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

General Tree:

struct Node 
{
  int val;
  vector<Node*> children;
  Node(int v) : val(v) {}
};

Declare the adjacency matrix of the graph $g$ and the array $u se d$ .

#define MAX 110
int g[MAX][MAX], used[MAX];

The dfs function performs a depth-first search starting from vertex $v$ . The parent of vertex $v$ is $p$ . If a cycle is detected, the $f l a g$ variable is set to $1$ .

void dfs(int v, int p)
{

If the graph is no longer a tree $(f l a g = 1)$ , there is no need to continue the search.

  if (flag) return;

Mark the vertex $v$ as visited.

  used[v] = 1;

The vertex $v$ is visited, increase $c$ by $1$ .

  c++;

The edge $(v, i)$ will be a back edge and form a cycle if $i \neq = p$ and vertex $i$ is already visited $(u se d [i] = 1)$ . If a cycle is detected, set $f l a g = 1$ . If no cycle is detected, continue the search from vertex $i$ .

  for(int i = 0; i < n; i++)
    if ((i != p) && g[v][i])
      if(used[i]) flag = 1; else dfs(i,v);
}

The main part of the program. Read the input data.

scanf("%d",&n); 
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
  scanf("%d",&g[i][j]);

Count the number of visited vertices during the depth-first search in the variable $c$ . Set $f l a g = 0$ if there is no cycle in the graph. If a cycle is detected, $f l a g$ becomes $1$ .

c = 0;
flag = 0;

All vertices are initially unvisited (initialize the array $u se d$ with zeroes).

memset(used,0,sizeof(used));

Start the depth-first search from vertex $0$ . Since it is the root of the tree, it has no parent. Pass the value $- 1$ as the second argument to the dfs function.

dfs(0,-1);

The graph is not a tree if there is a back edge $(f l a g = 1)$ or if the graph is not connected $(c \neq = n)$ .

if (flag || (c != n)) printf("NO\n"); else printf("YES\n");

Python implementation — checking the conditions 1) and 3)

The dfs function performs a depth-first search starting from vertex $v$ . The parent of vertex $v$ is $p$ . If a cycle is detected, the $f l a g$ variable is set to $1$ .

def dfs(v, p):

Declare the global variables used by the function.

  global flag, c

If the graph is no longer a tree $(f l a g = 1)$ , there is no need to continue the search.

  if flag: return

Mark the vertex $v$ as visited.

  used[v] = 1

The vertex $v$ is visited, increase $c$ by $1$ .

  c += 1

  for i in range(n):
    if i != p and g[v][i]:
      if used[i]: flag = 1
      else: dfs(i, v)

The main part of the program. Read the input value of $n$ .

n = int(input())

Count the number of visited vertices during the depth-first search in the variable $c$ . Set $f l a g = 0$ if there is no cycle in the graph. When a cycle is detected, $f l a g$ becomes $1$ .

c = 0
flag = 0

All vertices are initially unvisited (initialize the list $u se d$ with zeroes).

used = [0] * n

Create an adjacency matrix $g$ , initially filled with zeroes.

g = [[0] * n for _ in range(n)]

Read the input adjacency matrix.

for i in range(n):
  g[i] = list(map(int, input().split()))

Start the depth-first search from vertex $0$ . Since it is the root of the tree, it has no parent. Pass the value $- 1$ as the second argument to the dfs function.

dfs(0, -1)

The graph is not a tree if there is a back edge $(f l a g = 1)$ or if the graph is not connected $(c \neq = n)$ .

if flag or c != n:
  print("NO")
else:
  print("YES")

Declare the adjacency matrix of the graph $g$ and the array $u se d$ .

#define MAX 101
int g[MAX][MAX], used[MAX];

The dfs function implements depth-first search from vertex $v$ .

void dfs(int v)
{

Mark the vertex $v$ as visited.

  used[v] = 1;

Vertex $v$ is visited, increase $c$ by $1$ .

  c++;

Iterate over the vertices $i$ , that can be reached from $v$ . Moving from $v$ to $i$ is possible if:

There is an edge $(v, i)$ , that is $g [v] [i] = 1$ ;
The vertex $i$ is not visited $(u se d [i] = 0)$

If both conditions are true, we continue the depth-first search from vertex $i$ .

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) dfs(i);
}

The main part of the program. Read the input value of $n$ .

scanf("%d", &n);

Count the number of edges in the graph in the variable $E d g es$ .

Edges = 0;

All vertices are initially unvisited (initialize the array $u se d$ with zeroes).

memset(used, 0, sizeof(used));

Read the adjacency matrix $g$ . Count the number of edges in the graph.

for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
  scanf("%d", &g[i][j]);
  Edges += g[i][j];
}

Since the graph is undirected, edges $(u, v)$ and $(v, u)$ are considered the same. Divide the value of $E d g es$ by $2$ .

Edges /= 2;

Count the number of visited vertices during the depth-first search in variable $c$ .

c = 0;

Start the depth-first search from the vertex $1$ .

dfs(1);

The graph is a tree if the number of edges in it equals $n - 1$ , and also if it is connected $(c = n)$ .

if ((Edges == n - 1) && (c == n)) printf("YES\n");
else printf("NO\n");

Python implementation — checking the conditions 1) and 2)

The dfs function implements depth-first search from vertex $v$ .

def dfs(v):
  global c

Mark the vertex $v$ as visited.

  used[v] = 1

The vertex $v$ is visited, increase $c$ by $1$ .

  c += 1

Iterate over the vertices $i$ , that can be reached from $v$ . Moving from $v$ to $i$ is possible if:

There is an edge $(v, i)$ , that is $g [v] [i] = 1$ ;
The vertex $i$ is not visited $(u se d [i] = 0)$

If both conditions are true, we continue the depth-first search from vertex $i$ .

  for i in range(1, n + 1):
    if g[v][i] and not used[i]: dfs(i)

The main part of the program. Read the input value of $n$ .

n = int(input())

Count the number of edges in the graph in the variable $E d g es$ .

Edges = 0

All vertices are initially unvisited (initialize the array $u se d$ with zeroes).

used = [0] * (n + 1)

Create an adjacency matrix $g$ , initially filled with zeroes.

g = [[0] * (n + 1) for _ in range(n + 1)]

Read the adjacency matrix $g$ . Count the number of edges in the graph.

for i in range(1, n + 1):
  g[i] = [0] + list(map(int, input().split()))
  Edges += sum(g[i])

Since the graph is undirected, edges $(u, v)$ and $(v, u)$ are considered the same. Divide the value of $E d g es$ by $2$ .

Edges //= 2

Count the number of visited vertices during the depth-first search in variable $c$ .

c = 0

Start the depth-first search from the vertex $1$ .

dfs(1)

The graph is a tree if the number of edges in it equals $n - 1$ , and also if it is connected $(c = n)$ .

if Edges == n - 1 and c == n:
  print("YES")
else:
  print("NO")

The task is to decompose the tree into connected components with an even number of vertices, while maximizing the number of such components.

We'll perform a depth-first search starting from vertex $1$ , which is the root of the tree. For each vertex $v$ , we'll determine the number of vertices in the subtree rooted at $v$ . If this number is even, we'll remove the edge connecting $v$ to its parent in the depth-first search.

For the root (vertex $1$ ), the size of the entire tree is even. However, there is no edge connecting vertex $1$ to its parent, so we must subtract $1$ from the result obtained using the above algorithm.

Example

Consider the tree shown in the example. Next to each vertex is the size of the subtree when that vertex is considered as the root. Vertices $1, 3$ , and $6$ have subtrees with an even number of vertices. Since vertex $1$ is the root and does not have an edge leading to a parent, we remove two edges: $(1, 3)$ and $(1, 6)$ .

The tree has been decomposed into $3$ connected components, each containing an even number of vertices.

Declare the arrays.

#define MAX 101
int g[MAX][MAX], used[MAX];

The dfs function performs a depth-first search starting from vertex $v$ and returns the number of vertices in the subtree rooted at $v$ .

int dfs(int v)
{
  used[v] = 1;

In the variable $s$ , compute the number of vertices in the subtree rooted at $v$ .

  int s = 1;

Iterate over the children $i$ of vertex $v$ . Add the values of $df s (i)$ to $s$ .

  for (int i = 1; i <= n; i++)
    if (g[v][i] && !used[i]) s += dfs(i);

If the size of the subtree $s$ is even, remove the edge between $v$ and its parent.

  if (s % 2 == 0) res++;

Return the number of vertices in the subtree rooted at $v$ .

  return s;
}

The main part of the program. Read the input data and build the graph.

scanf("%d %d", &n, &m);
for (i = 0; i < m; i++)
{
  scanf("%d %d", &a, &b);
  g[a][b] = g[b][a] = 1;
}

Start a depth-first search from vertex $1$ . In the variable $res$ , count the number of removed edges.

res = 0;
dfs(1);

Since there is no edge from $1$ to its parent, print $res - 1$ .

printf("%d\n", res - 1);

Python implementation

The dfs function performs a depth-first search starting from vertex $v$ and returns the number of vertices in the subtree rooted at $v$ .

def dfs(v):
  used[v] = 1

In the variable $s$ , compute the number of vertices in the subtree rooted at $v$ .

  s = 1

Iterate over the children $i$ of vertex $v$ . Add the values of $df s (i)$ to $s$ .

  for i in range(1, n + 1):
    if g[v][i] and not used[i]:
      s += dfs(i)

If the size of the subtree $s$ is even, remove the edge between $v$ and its parent.

  if s % 2 == 0:
    global res
    res += 1

Return the number of vertices in the subtree rooted at $v$ .

  return s

The main part of the program. Read the input data and build the graph.

n, m = map(int, input().split())
g = [[0] * (n + 1) for _ in range(n + 1)]
used = [0] * (n + 1)

for _ in range(m):
  a, b = map(int, input().split())
  g[a][b] = g[b][a] = 1

Start a depth-first search from vertex $1$ . In the variable $res$ , count the number of removed edges.

res = 0
dfs(1)

Since there is no edge from $1$ to its parent, print $res - 1$ .

print(res - 1)

The tree is stored in the adjacency list $g$ .

vector<vector<int> > g;

The dfs function performs a depth-first search from vertex $v$ and returns the number of vertices in the subtree rooted at $v$ . Vertex $p$ is the parent of $v$ in the depth-first search.

int dfs(int v, int p)
{

Initially, the subtree rooted at $v$ contains only the vertex $v$ .

  sum[v] = 1;

Consider the edge $v \to t o$ . If $t o \neq = p$ , add to $s u m [v]$ the number of vertices in the subtree rooted at $t o$ .

  for (int to : g[v])
    if (to != p) sum[v] += dfs(to, v);

Return the number of vertices in the subtree rooted at $v$ .

  return sum[v];
}

The main part of the program. Read the input data. Construct a tree.

scanf("%d", &n);
g.resize(n + 1);

for (i = 2; i <= n; i++)
{
  scanf("%d", &x);

For employee $i$ , its immediate supervisor in the company is $x$ .

  g[i].push_back(x);
  g[x].push_back(i);
}

Start the depth-first search from vertex $1$ .

sum.resize(n + 1);
dfs(1, -1);

Print the answer. The number of subordinates of employee $i$ is equal to $s u m [i] -1$ .

for (i = 1; i <= n; i++)
  printf("%d ", sum[i] - 1);
printf("\n");

Java implementation

import java.util.*;

public class Main
{
  static ArrayList<Integer>[] g;	
  static int sum[];
  static int n;
  
  static int dfs(int v, int p)
  {
    sum[v] = 1;
    for(int to : g[v])
      if (to != p) sum[v] += dfs(to,v);
    return sum[v];
  }
  
  @SuppressWarnings("unchecked")
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    g = new ArrayList[n+1]; // unchecked
    sum = new int[n+1];

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Integer>();

    for (int i = 2; i <= n; i++)
    {
      int x = con.nextInt();
      g[i].add(x);
      g[x].add(i);
    }
    
    dfs(1,-1);
    for (int i = 1; i <= n; i++)
      System.out.print(sum[i] - 1 + " ");    
    System.out.println();
    con.close();
  }
}

Python implementation

Increase the stack for recursion.

import sys
sys.setrecursionlimit(1000000)

The dfs function performs a depth-first search from vertex $v$ and returns the number of vertices in the subtree rooted at $v$ . Vertex $p$ is the parent of $v$ in the depth-first search.

def dfs(v, p):

Initially, the subtree rooted at $v$ contains only the vertex $v$ .

  sum[v] = 1

Consider the edge $v \to t o$ . If $t o \neq = p$ , add to $s u m [v]$ the number of vertices in the subtree rooted at $t o$ .

  for to in g[v]:
    if to != p: sum[v] += dfs(to,v)

Return the number of vertices in the subtree rooted at $v$ .

  return sum[v]

The main part of the program. Read the number of employees.

n = int(input())

Initialize the adjacency list of the graph $g$ .

g = [[] for _ in range(n+1)]

Read the input data. Construct a tree.

lst = list(map(int, input().split()))
for i in range(2,n+1):
  a = lst[i-2]

For employee $i (i \geq 2)$ , its immediate supervisor in the company is $a$ .

  g[a].append(i)
  g[i].append(a)

Initialize the list $s u m$ .

sum = [0] * (n + 1)

Start the depth-first search from vertex $1$ .

dfs(1,-1)

Print the answer. The number of subordinates of employee $i$ is equal to $s u m [i] - 1$ .

for i in range(1, n+1):
  print(sum[i] - 1,end=" ")

Store the input tree in the adjacency list $g$ . Store the shortest distances from the source to each vertex in the array $d i s t$ .

vector<vector<int>> g;
vector<int> dist;

The dfs function performs a depth-first search from vertex $v$ . The shortest distance from the source to vertex $v$ is $d$ . The parent of vertex $v$ in the depth-first search is $p$ .

void dfs(int v, int d, int p = -1)
{

Store the shortest distance from the source to vertex $v$ in $d i s t [v]$ .

  dist[v] = d;

Iterate over all edges $(v, t o)$ . For each son to of vertex $v$ (where $t o$ is not a parent of $v$ ) initiate a depth-first search. The distance from the source to vertex $t o$ will be $d + 1$ .

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, v);
}

The main part of the program. Read the input data.

scanf("%d", &n);
g.resize(n + 1);
dist.resize(n + 1);

Construct an undirected tree.

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

Find the shortest distances from vertex $1$ to all other vertices. The vertex farthest from it is $a$ .

dfs(1, 0, -1);
a = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Find the shortest distances from vertex $b$ to all other vertices. The vertex farthest from it is $b$ .

dfs(a, 0,  -1);
b = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Print the diameter of the tree — the shortest distance from $a$ to $b$ .

printf("%d\n", dist[b]);

The input tree is stored as an adjacency list $g$ .

The shortest distances from vertices $a$ and $b$ are stored in the arrays $d i s t a$ and $d i s t b$ , respectively.

vector<vector<int>> g;
vector<int> dista, distb;

The function dfs performs a depth-first search starting from vertex $v$ .

The parameter $d$ represents the shortest distance from the source to vertex $v$ .
The results are stored in the array $d i s t$ .
The parameter $p$ indicates the parent of vertex $v$ during the traversal.

void dfs(int v, int d, vector<int>& dist, int p = -1)
{

Store the shortest distance from the source to vertex $v$ in $d i s t [v]$ .

  dist[v] = d;

Iterate over all edges $(v, t o)$ . For each child $t o$ of vertex $v$ (i.e., a vertex to that is not the parent of $v$ ), perform a depth-first search.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, dist, v);
}

The main part of the program. Read the input data.

scanf("%d", &n);
g.resize(n + 1);
dista.resize(n + 1);
distb.resize(n + 1);

Construct an undirected tree.

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

Compute the shortest distances from vertex $1$ . The vertex farthest from it is vertex $a$ .

dfs(1, 0, dista, -1);
a = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Next, compute the shortest distances from vertex $a$ and store them in the array $d i s t a$ . The vertex farthest from $a$ turns out to be vertex $b$ . The distance between vertices $a$ and $b$ is the diameter of the tree.

dfs(a, 0, dista, -1);
b = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Then compute the shortest distances from vertex $b$ and store them in the array $d i s t b$ .

dfs(b, 0, distb, -1);

For each vertex $i$ , print the distance to the farthest vertex from it.

for (i = 1; i <= n; i++)
  printf("%d ", max(dista[i], distb[i]));
printf("\n");

Python implementation

Increase the recursion stack size.

import sys
sys.setrecursionlimit(1000000)

The function dfs performs a depth-first search starting from vertex $v$ .

The parameter $d$ represents the shortest distance from the source to vertex $v$ .
The results are stored in the array $d i s t$ .
The parameter $p$ indicates the parent of vertex $v$ during the traversal.

def dfs(v, d, dist, p =- 1):

Store the shortest distance from the source to vertex $v$ in $d i s t [v]$ .

  dist[v] = d

Iterate over all edges $(v, t o)$ . For each child $t o$ of vertex $v$ (i.e., a vertex to that is not the parent of $v$ ), perform a depth-first search.

  for to in g[v]:
    if to != p:
      dfs(to, d + 1, dist, v)

The main part of the program. Read the input data.

n = int(input())
g = [[] for _ in range(n + 1)]
dista = [0] * (n + 1)
distb = [0] * (n + 1)

Construct an undirected tree.

for _ in range(n - 1):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)

Compute the shortest distances from vertex $1$ . The vertex farthest from it is vertex $a$ .

dfs(1, 0, dista)
a = dista.index(max(dista[1:]))

dfs(a, 0, dista)
b = dista.index(max(dista[1:]))

Then compute the shortest distances from vertex $b$ and store them in the array $d i s t b$ .

dfs(b, 0, distb)

For each vertex $i$ , print the distance to the farthest vertex from it.

result = [max(dista[i], distb[i]) for i in range(1, n + 1)]
print(*result)

Roman's parents gave him an undirected, connected, weighted graph with $n$ vertices and $n - 1$ edges. Roman wants to find the total length of all paths between every pair of vertices in the graph. The length of a path is defined as the sum of the weights of the edges it includes. Since the path from vertex $u$ to vertex $v$ is the same as the path from $v$ to $u$ , Roman treats them as a single path and does not distinguish between them.

Input. The first line contains an integer $n (2 \leq n \leq 1 0^{5})$ — the number of vertices in the graph.

Each of the next $n - 1$ lines describes an edge and contains three integers: the numbers of the two vertices connected by the edge (vertices are numbered from $1$ to $n$ ), and the weight of the edge.

Output. Print the total length of all distinct paths between all pairs of vertices, modulo $1 0^{9}$ .

Open problem

Perform a depth-first search starting from an arbitrary vertex of the tree. Consider an edge $(u, v)$ with weight $w$ . Let the number of vertices in the subtree rooted at $v$ be $c$ . Then, there are $c$ vertices on one side of the edge and $n - c$ vertices on the other side. The edge $(u, v)$ is included in $c \cdot (n - c)$ distinct paths between pairs of vertices. Therefore, its contribution to the total length of all paths is $c \cdot (n - c) \cdot w$ . We just need to iterate over all edges using depth-first search and sum up their contributions to the overall path length.

Example

The graphs given in the examples have the following structure:

Consider the contribution of the edges to the total length of all paths in the first example.

The edge $(1, 2)$ with weight $1$ belongs to two paths:

$1 - 2$ ;
$2 - 1 - 3$ ;

Its contribution to the total sum is $1 \cdot 2 \cdot 1 = 2$ .

The edge $(1, 3)$ with weight $3$ belongs to two paths:

$1 - 3$ ;
$2 - 1 - 3$ ;

Its contribution to the total sum is $2 \cdot 1 \cdot 3 = 6$ .

The total length of all paths is $2 + 6 = 8$ .

In the second example, let us consider the contribution of the edge $(1, 2)$ with weight $5$ to the total length of all paths.

The number of vertices in the subtree rooted at vertex $2$ is $c = 4$ (including vertex $2$ itself). Then, on the other side of the edge $(1, 2)$ there are $n - c = 6 - 4 = 2$ vertices. Therefore, the number of distinct paths passing through the edge $(1, 2)$ is $c \cdot (n - c) = 4 \cdot 2 = 8$ .

Indeed, these are all pairs of vertices where one lies in the subtree of vertex $2$ , and the other lies outside of it:

1 - 2, 1 - 2 - 4, 1 - 2 - 5, 1 - 2 - 6, 3 - 1 - 2, 3 - 1 - 2 - 4, 3 - 1 - 2 - 5, 3 - 1 - 2 - 6

The contribution of the edge $(1, 2)$ with weight $5$ to the total length of all paths is

c \cdot (n - c) \cdot w = 4 \cdot 2 \cdot 5 = 40

Declare the value of the modulo as $MO D$ .

#define MOD 1000000000

The input weighted graph is stored in an adjacency list $g$ .

vector<vector<pair<int,int> > > g;

The function dfs performs a depth-first search starting from vertex $v$ and returns the number of vertices in the subtree rooted at $v$ (including $v$ itself). The number of such vertices is counted in the variable $c n t$ . Initially, set $c n t = 1$ since the subtree already includes vertex $v$ .

int dfs(int v, int p = -1)
{
  int cnt = 1;
  for (auto edge : g[v])
  {
    int to = edge.first;
    int w = edge.second;

Consider the edge $(v, t o)$ with weight $w$ . Let $c$ be the number of vertices in the subtree rooted at vertex $t o$ . Then, one side of the edge contains $c$ vertices, and the other side contains $n - c$ vertices. The edge $(v, t o)$ is included in $c \cdot (n - c)$ different paths between pairs of vertices. Thus, the contribution of the edge $(v, t o)$ to the total length of all paths is

c \cdot (n - c) \cdot w

    if (to != p)
    {
      int c = dfs(to, v);
      res = (res + 1LL * c * (n - c) * w) % MOD;
      cnt += c;
    }
  }
  return cnt;
}

The main part of the program. Read the input weighted graph into the adjacency list $g$ .

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

Start a depth-first search from vertex $1$ . The vertices of the graph are numbered from $1$ to $n$ .

dfs(1);

Print the answer.

printf("%lld\n",res);

Java implementation

import java.util.*;
import java.io.*;

class Edge 
{
  int to;
  int weight;
  public Edge(int to, int weight) 
  {
    this.to = to;
    this.weight = weight;
  }
}

public class Main
{
  static int MOD = 1000000000;
  static ArrayList<Edge>[] g;	
  static int n, m;
  static long res;
  
  static int dfs(int v, int p)
  {
    int cnt = 1;
    for(Edge edge : g[v])
    {
      int to = edge.to;
      int w = edge.weight;
      if (to != p)
      {
        int c = dfs(to, v);
        res = (res + 1L * c * (n - c) * w) % MOD;
        cnt += c;
      }
    }
    return cnt;
  }
  
  public static void main(String[] args)
  {
    FastScanner con = new FastScanner(System.in);
    n = con.nextInt();
    g = new ArrayList[n+1]; // unchecked

    for (int i = 0; i <= n; i++)
      g[i] = new ArrayList<Edge>();

    for (int i = 1; i < n; i++)
    {
      int u = con.nextInt();
      int v = con.nextInt();
      int d = con.nextInt();
      g[u].add(new Edge(v,d));
      g[v].add(new Edge(u,d));
    }
    
    dfs(1,-1);
    System.out.println(res);    
  }
}   

class FastScanner 
{
  BufferedReader br;
  StringTokenizer st;

  public FastScanner(InputStream inputStream) 
  {
    br = new BufferedReader(new InputStreamReader(inputStream));
    st = new StringTokenizer("");
  }

  public String next() 
  {
    while (!st.hasMoreTokens()) 
    {
      try 
      {
        st = new StringTokenizer(br.readLine());
      } catch (Exception e) 
      {
        return null;
      }
    }
    return st.nextToken();
  }
 
  public int nextInt() 
  {
    return Integer.parseInt(next());
  }
}

Python implementation

Declare the value of the modulo as $MO D$ .

MOD = 1000000000

def dfs(v, p = -1):
  global res
  cnt = 1
  for to, w in g[v]:

c \cdot (n - c) \cdot w

    if to != p:
      c = dfs(to, v)
      res = (res + c * (n - c) * w) % MOD
      cnt += c
  return cnt

The main part of the program. Read the input data.

n = int(input())
g = [[] for _ in range(n + 1)]
res = 0

for _ in range(n - 1):
  u, v, d = map(int, input().split())
  g[u].append((v, d))
  g[v].append((u, d))

Start a depth-first search from vertex $1$ . The vertices of the graph are numbered from $1$ to $n$ .

dfs(1)

Print the answer.

print(res)

The array $co l or [i]$ stores the color of vertex $i$ . The set $s [i]$ will accumulate the colors that appear in the subtree rooted at vertex $i$ .

The directed tree is represented as an adjacency list $g$ . The array $res [i]$ stores the number of distinct colors in the subtree rooted at vertex $i$ .

#define MAX 1000010
int color[MAX], res[MAX];
set<int> s[MAX];
vector<vector<int> > g;

The function dfs performs a depth-first traversal of the tree starting from vertex $v$ .

void dfs(int v)
{

First, the color of vertex $v$ itself is added to the set $s [v]$ .

  s[v].insert(color[v]);

Iterate over the tree edges $(v, t o)$ .

  for (int to : g[v])
  {
    dfs(to);

For each edge $(v, t o)$ , merge the set $s [t o]$ into $s [v]$ . If the size of $s [v]$ is smaller than the size of $s [t o]$ , swap them first. Then, the content of the smaller set $s [t o]$ is added to the larger set $s [v]$ .

    if (s[v].size() < s[to].size()) s[v].swap(s[to]);
    s[v].insert(s[to].begin(), s[to].end());

Clear the set $s [t o]$ — it is no longer needed.

    s[to].clear();
  }

After that, store the number of distinct colors in the subtree in $res [v]$ , which is the size of the set $s [v]$ .

  res[v] = s[v].size();
}

The main part of the program. Read the input data.

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

Start the depth-first search from the root of the tree — the vertex with index $0$ .

dfs(0);

Print the answer.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");

After a long and busy work week, the residents of Manchester and Liverpool decided to go hiking for the weekend. While walking through the forest, they came across a unique tree consisting of $n$ vertices. The vertices of the tree are numbered from $1$ to $n$ , and each one is painted in one of $c$ possible colors.

To fight off boredom, they decided to test their logical thinking. The root of the tree is vertex $1$ . For each vertex, the participants decided to find its nearest ancestor that shares the same color.

Input. The first line contains two integers $n$ and $c (1 \leq n, c \leq 1 0^{5})$ — the number of vertices in the tree and the number of possible colors.

The second line contains $n - 1$ integers: the $i$ -th of them indicates the parent of vertex $i + 1$ .

The third line contains $n$ integers — the colors of the vertices. Each color is an integer from $1$ to $c$ , inclusive.

Output. Print $n$ integers in a single line: for each vertex, print the number of its nearest ancestor with the same color. If no such ancestor exists, print $- 1$ .

Open problem

Let us consider a simplified version of the problem. Suppose all the vertices of the tree are painted the same color. We initialize an empty stack and perform a depth-first search starting from the root of the tree. When entering a vertex $v$ , push it onto the stack. When the processing of vertex $v$ is complete, remove the top element from the stack (which will be vertex $v$ itself). After the DFS is finished, the stack will once again be empty.

Question: What will be on the top of the stack at the moment we enter vertex $v$ , just before we push $v$ onto the stack?

Now let us move on to solving the original problem. We create $c$ stacks — one for each color (for example, using a vector of stacks). Initially, all stacks are empty. Perform a DFS starting from the root of the tree — vertex $1$ . The processing of a vertex $v$ , painted in color $co l or$ , includes the following steps:

If the stack $s [co l or]$ is not empty, its top element contains the number of the vertex that is the nearest ancestor of vertex $v$ with the same color. If the stack is empty, such a vertex does not exist, and the answer for vertex $v$ should be $- 1$ .
Push vertex $v$ onto the stack $s [co l or]$ .
Recursively perform a depth-first search from all children of vertex $v$ .
After finishing the processing of vertex $v$ , remove it from the stack $s [co l or]$ .

During the depth-first search, when we are at vertex $v$ , the stacks contain information about the colors of all vertices along the unique path from the root to vertex $v$ . In particular, the stack $s [co l or]$ stores the numbers of all vertices on this path that are colored with $co l or$ . These vertices are pushed onto the stack in the order they are visited during the DFS.

Example

When the depth-first search reaches vertex $5$ , two out of the $c = 4$ stacks will be empty (those corresponding to colors $3$ and $4$ ).

Stack number $1$ (for color $1$ ) will contain vertex $1$ , and stack number $2$ (for color $2$ ) will contain vertex $3$ . Since vertex $5$ has color $2$ , its nearest ancestor with the same color is at the top of stack number $2$ .

Therefore, the nearest ancestor of vertex $5$ with the same color is vertex $3$ .

Declare the arrays.

vector<int> col, res;
vector<vector<int> > g;
vector<stack<int> > s;

The dfs function performs a depth-first search starting from vertex $v$ .

void dfs(int v)
{

Vertex $v$ has color $co l or$ .

  int color = col[v];

The number of the nearest ancestor of vertex $v$ with the same color is stored in $res [v]$ .

  if(s[color].empty())
    res[v] = -1;
  else
    res[v] = s[color].top();

Push vertex $v$ onto the stack corresponding to its color.

  s[color].push(v);

Iterate over all children $t o$ of vertex $v$ and recursively perform a depth-first search from each of them.

  for (int to : g[v])
    dfs(to);

After processing vertex $v$ is complete (i.e., upon exiting it), remove it from the stack corresponding to its color.

  s[color].pop();
}

The main part of the program. Read the input data. Construct a tree.

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

Read the colors of the tree's vertices.

col.resize(n + 1);
for(i = 1; i <= n; i++)
  scanf("%d",&col[i]);

Start a depth first search from vertex $1$ .

s.resize(c + 1);
res.resize(n + 1);
dfs(1);

Print the answer.

for(i = 1; i <= n; i++)
  printf("%d ",res[i]);
printf("\n");

Python implementation

Increase the recursion stack size.

import sys
sys.setrecursionlimit(1000000)

The dfs function performs a depth-first search starting from vertex $v$ .

def dfs(v):

Vertex $v$ has color $co l or$ .

  color = col[v]

The number of the nearest ancestor of vertex $v$ with the same color is stored in $res [v]$ .

  if not s[color]:
    res[v] = -1
  else:
    res[v] = s[color][-1]

Push vertex $v$ onto the stack corresponding to its color.

  s[color].append(v)

Iterate over all children $t o$ of vertex $v$ and recursively perform a depth-first search from each of them.

  for to in g[v]:
    dfs(to)

After processing vertex $v$ is complete (i.e., upon exiting it), remove it from the stack corresponding to its color.

  s[color].pop()

The main part of the program. Read the input data. Construct a tree.

n, c = map(int, input().split())
lst = list(map(int, input().split()))
g = [[] for _ in range(n + 1)]
for i in range(2, n + 1):
  val = lst[i - 2]
  g[val].append(i)

Read the colors of the tree's vertices.

col = [0] * (n + 1)
col[1:] = list(map(int, input().split()))

Start a depth first search from vertex $1$ .

s = [[] for _ in range(c + 1)]
res = [0] * (n + 1)
dfs(1)

Print the answer.

print(*res[1:])

In his spare time, Farmer John created his own video-sharing platform called MooTube. On MooTube, his cows can record, publish, and discover lots of funny videos. So far, the cows have uploaded $n$ videos, numbered from $1$ to $n$ .

However, Farmer John doesn't fully understand how to help his cows find new videos they might enjoy. He wants to implement a recommendation system for each video — a list of "recommended videos" based on their similarity to videos already watched.

To determine how similar two videos are, John introduces a relevance metric. He manually evaluates $n - 1$ pairs of videos and assigns each pair a relevance score. Using these pairs, John builds a network where each video is a node in a graph, and the selected pairs are connected by edges with the given relevance values.

For convenience, John selects the $n - 1$ pairs in such a way that there is exactly one path between any two videos — in other words, the video network forms a tree.

He decides that the relevance between two videos should be defined as the minimum relevance among all edges along the path connecting them.

Now, Farmer John wants to choose a value $k$ such that, for any video on MooTube, all other videos with relevance at least $k$ to it will be displayed as recommendations. However, he worries that too many recommendations might distract his cows from producing milk, so he wants to precisely estimate how many videos would be recommended for various values of $k$ .

Farmer John turns to you for help: you are given several queries, each consisting of a value $k$ and a video number. For each query, you need to determine how many other videos would be recommended if the minimum required relevance is $k$ .

Input. The first line contains two integers $n$ and $q (1 \leq n, q \leq 5000)$ — the number of videos and the number of queries, respectively.

The next $n - 1$ lines describe pairs of videos whose relevance has been manually evaluated by Farmer John. Each of these lines contains three integers $p_{i}, q_{i}$ и $r_{i} (1 \leq p_{i}, q_{i} \leq n, 1 \leq r_{i} \leq 1 0^{9})$ , , meaning that videos $p_{i}$ and $q_{i}$ are connected by an edge with relevance $r_{i}$ .

Then follow $q$ lines, each describing one of Farmer John’s queries. The $i$ -th line contains two integers $k_{i}$ and $v_{i} (1 \leq k_{i} \leq 1 0^{9}, 1 \leq v_{i} \leq n)$ — meaning that in the $i$ -th query, Farmer John wants to know how many videos will be recommended for video $v_{i}$ if the minimum acceptable relevance for recommendations is $k = k_{i}$ .

Output. Print $q$ lines. In the $i$ -th line, output the answer to Farmer John's $i$ -th query.

Example. Farmer John has established the following connections between videos:

Video $1$ and video $2$ have a relevance of $3$ ,
Video $2$ and video $3$ have a relevance of $2$ ,
Video $2$ and video $4$ have a relevance of $4$ .

Based on this data, we can compute the relevance between other pairs of videos:

Video $1$ and video $3$ : relevance = $min (3, 2) = 2$ ,
Video $1$ and video $4$ : relevance = $min (3, 4) = 3$ ,
Video $3$ and video $4$ : relevance = $min (2, 4) = 2$ .

Now let’s see which videos will be recommended for the following queries:

From video $2$ with $k = 1$ , videos $1, 3$ , and $4$ will be recommended.
From video $1$ with $k = 3$ , videos $2$ and $4$ will be recommended.
From video $1$ with $k = 4$ , no videos will be recommended.

Open problem

For each query given by the pair $(k_{i}, v_{i})$ , perform a depth-first or breadth-first search starting from vertex $v_{i}$ . During the traversal, only follow edges whose relevance is at least $k_{i}$ .

Count the number of reachable vertices $res$ , excluding the starting vertex $v_{i}$ . The value of $res$ is the answer to the query $(k_{i}, v_{i})$ .

Example

Farmer John has established the following connections between videos:

Video $1$ and video $2$ have a relevance of $3$ ,
Video $2$ and video $3$ have a relevance of $2$ ,
Video $2$ and video $4$ have a relevance of $4$ .

Based on this data, we can compute the relevance between other pairs of videos:

Video $1$ and video $3$ : relevance = $min (3, 2) = 2$ ,
Video $1$ and video $4$ : relevance = $min (3, 4) = 3$ ,
Video $3$ and video $4$ : relevance = $min (2, 4) = 2$ .

Now let’s see which videos will be recommended for the following queries:

From video $2$ with $k = 1$ , videos $1, 3$ , and $4$ will be recommended.
From video $1$ with $k = 3$ , videos $2$ and $4$ will be recommended.
From video $1$ with $k = 4$ , no videos will be recommended.

Store the input graph in an adjacency list $g$ .

vector<vector<pair<int, int>>> g;

The bfs function performs a breadth-first search starting from the vertex $s t a r t$ and returns the number of visited vertices, excluding the vertex $s t a r t$ itself. During the search, we only move along edges whose weight is at least the given value $k$ .

int bfs(int start, int k)
{

The shortest distance array is not needed in this problem — it's sufficient to simply track whether a vertex is visited. If vertex $i$ is visited, set $u se d [i] = 1$ .

  vector<int> used(n + 1);
  used[start] = 1;

Initialize a queue and add the starting vertex $s t a r t$ to it.

  queue<int> q;
  q.push(start);

The number of visited vertices during the breadth-first search (excluding the starting vertex $s t a r t$ ) is counted in the variable $res$ .

  int res = 0;

Start the breadth-first search.

  while (!q.empty())
  {

Extract the vertex $v$ from the queue $q$ .

    int v = q.front(); q.pop();

Iterate over all edges adjacent to vertex $v$ .

    for (auto edge : g[v])
    {

Consider the edge $(v, t o)$ with weight $k t o$ .

     int to = edge.first;
     int kto = edge.second;

If the edge weight $k t o$ is less than $k$ , skip this edge (moving along it is forbidden).

      if (kto < k) continue;

If the vertex $t o$ is not visited yet, add it to the queue, mark it as visited, and increment the counter $res$ by $1$ .

      if (used[to] == 0)
      {
        q.push(to);
        used[to] = 1;
        res++;
      }
    }
  }

Return the answer to the query.

  return res;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Add an undirected edge $(p, q)$ with weight $r$ to the adjacency list.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Process the $q u$ queries one by one.

while (qu--)
{
  scanf("%d %d", &k, &v);

Perform a breadth-first search (BFS) starting from vertex $v$ and print the number of vertices visited during the BFS.

  printf("%d\n", bfs(v, k));
}

Algorithm implementation — depth first search

Store the input graph in an adjacency list $g$ .

vector<vector<pair<int, int>>> g;

The dfs function performs a depth-first search starting from vertex $v$ and returns the number of visited vertices. During the search, we only traverse edges whose weight is not less than the given value $k$ .

int dfs(int v, int k)
{

Mark vertex $v$ as visited.

  used[v] = 1;

Count the number of vertices visited in the subtree rooted at $v$ during the depth-first search in the variable $res$ .

  int res = 1;

Iterate over all edges adjacent to vertex $v$ .

  for (auto edge : g[v])
  {

Consider the edge $(v, t o)$ with weight $k t o$ .

    int to = edge.first;
    int kto = edge.second;

If the weight $k t o$ is less than $k$ , skip this edge (moving along it is forbidden).

    if (kto < k) continue;

If vertex $t o$ is not visited yet, perform a depth-first search starting from it. The number of vertices visited in the subtree rooted at $t o$ is added to $res$ .

    if (used[to] == 0)
      res += dfs(to, k);
  }
  return res;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &qu);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d %d", &p, &q, &r);

Add an undirected edge $(p, q)$ with weight $r$ to the adjacency list.

  g[p].push_back({ q, r });
  g[q].push_back({ p, r });
}

Process the $q u$ queries one by one.

while (qu--)
{
  scanf("%d %d", &k, &v);

Perform a depth-first search starting from vertex $v$ . Print the number of vertices visited during the depth-first search, excluding the starting vertex $v$ .

  used.assign(n + 1, 0);
  printf("%d\n", dfs(v, k) - 1);
}

Using depth-first search, compute the XOR sum between vertex $1$ and all other vertices. Store the XOR sum between vertex $1$ and $v$ in $x [v]$ . Let $o n es$ be the number of ones and $zeroes$ be the number of zeros in the array $x (o n es + zeroes = n)$ . Then the answer to the problem will be $o n es \cdot zeroes$ .

Example

Consider the graph provided in the example.

Next to each vertex $v$ , the XOR sum $x [v]$ between $1$ and $v$ is written. If $x [v] = x [u]$ for some vertices $v$ and $u$ , then the XOR sum between them is equal to $0$ , thus contributing $0$ to the total sum. The XOR sum for each pair of vertices $(v, u)$ , for which $x [v] \neq = x [u]$ , contributes $1$ to the total sum.

Therefore, the answer is equal to the number of pairs of vertices $(v, u)$ for which $x [v] \neq = x [u]$ . This number is equal to $o n es \cdot zeroes = 2 \cdot 3 = 6$ . The pairs of vertices that contribute $1$ to the total sum are: $(1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5)$ .

Store the input graph in the adjacency list $g$ . Declare an array $x$ .

vector<vector<pair<int,int> > > g;
vector<int> x;

The dfs function implements a depth-first search that computes the XOR sum $x [v]$ between vertices $1$ and $v$ . The current XOR sum between $1$ and $v$ is represented by $c u r_x or$ . The parent of vertex $v$ is $p$ .

void dfs(int v, int cur_xor, int p = -1)
{
  x[v] = cur_xor;
  for (auto z : g[v])
  {
    int to = z.first;
    int w = z.second;
    if (to != p) dfs(to, cur_xor ^ w, v);
  }
}

The main part of the program. Read the input graph.

scanf("%d", &n);
g.resize(n + 1);
x.resize(n + 1);

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

Start the depth-first search from vertex $1$ .

dfs(1, 0, -1);

Compute the number of $zeroes$ and $o n es$ in the array $x$ .

ones = 0;
for (i = 1; i <= n; i++)
  if (x[i] == 1) ones++;
zeroes = n - ones;

Print the answer.

printf("%lld\n", 1LL * ones * zeroes);

Python implementation

def dfs(v, cur_xor = 0, p = -1):
  x[v] = cur_xor
  for to, w in g[v]:
    if to != p:
      dfs(to, cur_xor ^ w, v)

The main part of the program. Read the input graph.

n = int(input())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  u, v, d = map(int, input().split())
  g[u].append((v, d))
  g[v].append((u, d))

Initialize the list $x$ .

x = [0] * (n + 1)

Start the depth-first search from vertex $1$ .

dfs(1)

Compute the number of $zeroes$ and $o n es$ in the array $x$ .

ones = sum(x)
zeroes = n - ones

Print the answer.

print(ones * zeroes)

A tree with $n$ vertices numbered from $1$ to $n$ is given. The $i$ -th edge of the tree connects vertices $a_{i}$ and $b_{i}$ . Vertex $i$ is colored with color $c_{i}$ (in this problem, colors are represented by integers).

A vertex $x$ is considered good if the shortest path from vertex $1$ to vertex $x$ does not contain any other vertex with the same color as vertex $x$ , except for $x$ itself.

Find all good vertices.

Input. The first line contains an integer $n (2 \leq n \leq 1 0^{5})$ — the number of vertices.

The second line contains $n$ integers — the colors of the vertices: $c_{1}, c_{2}, \dots, c_{n} (1 \leq c_{i} \leq 1 0^{5})$ .

Each of the following $n - 1$ lines contains two integers $a_{i}$ and $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ — the edges of the tree.

Output. Print all good vertices, one per line, in ascending order of their indices.

Open problem

Store the input graph in the adjacency list $g$ . Declare the arrays.

vector<int> used, color;
vector<vector<int>> g;
set<int> st;

The dfs function implements depth-first search. The variable $p a r$ is the parent of vertex $v$ .

void dfs(int v, int par)
{

Vertex $v$ has the color $co l or [v]$ . Mark that a vertex with this color is visited on the path from vertex $1$ .

  used[color[v]]++;

The value $u se d [co l or [v]]$ indicates how many times the color $co l or [v]$ has appeared on the path from vertex $1$ to vertex $v$ (inclusive). If this color appears exactly once on the path, then vertex $v$ is considered good, and we add it to the result set $s t$ .

  if (used[color[v]] == 1) st.insert(v);

Iterate over all edges $(v, t o)$ originating from vertex $v$ . If vertex $t o$ is not the parent of $v (t o \neq = p a r)$ , start a depth-first search from $t o$ . In this case, the parent of $t o$ becomes $v$ .

  for (int to : g[v])
    if (to != par) dfs(to, v);

When exiting vertex $v$ , decrement the value of $u se d [co l or [v]]$ by $1$ .

  used[color[v]]--;
}

The main part of the program. Read the number of vertices $n$ and the array of colors.

scanf("%d", &n);
color.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &color[i]);

Read the graph.

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

Start a depth-first search from vertex $1$ .

dfs(1, 1);

Print the good vertices. They are contained in the set $s t$ .

for (int val : st)
  printf("%d\n", val);

You are given a tree with $n$ vertices and $n - 1$ edges. The vertices are numbered from $1$ to $n$ , and the $i$ -th edge connects vertices $a_{i}$ and $b_{i}$ .

You have $k$ colors available. For each vertex in the tree, you choose one of the $k$ colors to paint it, subject to the following condition:

If the distance between two different vertices $x$ and $y$ is less than or equal to two, then $x$ and $y$ have different colors.

How many ways are there to color the tree? Find the answer modulo $1 0^{9} + 7$ .

Input. The first line contains two numbers $n$ and $k (1 \leq n, k \leq 1 0^{5})$ . Each of the following $n - 1$ lines contains two integers $a_{i}$ and $b_{i} (1 \leq a_{i}, b_{i} \leq n)$ .

Output. Print the number of ways to color the tree modulo $1 0^{9} + 7$

Open problem

Let's start coloring the tree from vertex $1$ . It can be colored with $k$ colors.

Suppose we are at vertex $v$ . If it has no parent ( $v = 1$ ), then its children can be colored with $k - 1$ colors. If $v$ has a parent, then its children can be colored with $k - 2$ colors. Since the distance between the children of vertex $v$ is $2$ , they cannot be colored with the same color.

If vertex $v$ has a parent, then the first child of $v$ can be colored with $k - 2$ colors, the second child with $k - 3$ colors, and so on.

It remains to multiply the numbers of colors that can be used to color each vertex.

Example

For the first example, there are $6$ ways of coloring:

Let's consider the second test. Next to each vertex, we'll indicate the number of colors it can be colored with. For example, vertex $5$ can be colored with $2$ colors, as its color must not match the colors of vertices $1$ and $4$ . The total number of ways to color the tree is equal to $4 \cdot 3 \cdot 2 \cdot 1 \cdot 2 = 48$ .

Store the input graph in the adjacency list $g$ . Declare a constant $MO D$ for the modulo.

#define MOD 1000000007
vector<vector<int>> g;

The dfs function returns the number of ways to color the tree rooted at vertex $v$ modulo $MO D = 1 0^{9} + 7$ . The parent of vertex $v$ is $p$ . Vertex $v$ can be colored with $co l$ colors.

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

We are at vertex $v$ . In the variable $c n t$ , we keep track of the number of colors that cannot be used to paint the children of vertex $v$ . Initially, set $c n t = 1$ , since the children of vertex $v$ cannot have the same color as vertex $v$ . If vertex $v$ has a parent ( $p \neq = - 1$ ), then the children of vertex $v$ also cannot have the color of $v$ 's parent.

  int cnt = 1;
  if (p >= 0) cnt++;

Iterate over the sons $t o$ of the vertex $v$ .

  for (int to : g[v])
    if (to != p)
    {

The vertex $t o$ can be colored with $k - c n t$ colors. With each son, the $c n t$ value will be increased by $1$ .

      res = (res * dfs(to, k - cnt, v)) % MOD;
      cnt++;
    }
  return res;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &k);
g.resize(n + 1);
for (i = 0; i < n - 1; i++)
{
  scanf("%d %d", &a, &b);
  g[a].push_back(b);
  g[b].push_back(a);
}

Start the depth-first search from vertex $1$ . Vertex number $1$ can be colored with $k$ colors.

res = dfs(1, k);

Print the answer.

printf("%lld\n", res);

Python implementation

Set the maximum depth of the Python interpreter stack to the specified limit.

import sys
sys.setrecursionlimit(1000000)

Declare a constant $MO D$ for the modulo.

MOD = 1000000007

The dfs function returns the number of ways to color the tree rooted at vertex $v$ modulo $MO D = 1 0^{9} + 7$ . The parent of vertex $v$ is $p$ . Vertex $v$ can be colored with $co l$ colors.

def dfs(v, col, p = -1):
  res = col

  cnt = 1
  if p >= 0: cnt += 1

Iterate over the sons $t o$ of the vertex $v$ .

  for to in g[v]:
    if to != p:

The vertex $t o$ can be colored with $k - c n t$ colors. With each son, the $c n t$ value will be increased by $1$ .

      res = (res * dfs(to, k - cnt, v)) % MOD
      cnt += 1
  return res

The main part of the program. Read the input data.

n, k = map(int, input().split())
g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

Start the depth-first search from vertex $1$ . Vertex number $1$ can be colored with $k$ colors.

res = dfs(1, k)

Print the answer.

print(res)

There are $n$ cities in the country and $n - 1$ bidirectional roads, such that it is possible to travel from any city to any other city using only these roads. The cities are numbered with integers from $1$ to $n$ inclusive.

Initially, all roads are considered to be in bad condition, but the government plans to improve the state of some of them. The citizens will be satisfied with the improvements if there is no more than one bad road on the path from the capital, located in city $1$ , to any other city.

Determine the number of ways to improve the quality of some roads to meet this requirement. Since the answer can be very large, output it modulo $1 0^{9} + 7$ .

Input. The first line contains a single integer $n (2 \leq n \leq 2 \cdot 1 0^{5})$ — the number of cities in the country. The second line contains $n - 1$ positive integers $p_{2}, p_{3}, p_{4}, \dots, p_{n} (1 \leq p_{i} \leq i - 1)$ , describing the roads in the country. The number $p_{i}$ indicates that there is a road connecting city $p_{i}$ and city $i$ .

Output. Print the number of ways to improve the quality of the roads modulo $1 0^{9} + 7$ .

Open problem

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)$ remains in bad condition, then all roads in the subtree rooted at vertex $t o$ must be improved.
If the road $(v, t o)$ 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}$ 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)

If $v$ is a leaf (a vertex with no children), then let $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.

All calculations are performed modulo $MO D = 1 0^{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}$ 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)

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

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

Compute and print the result.

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

On clear summer days, Nyusha enjoys catching butterflies in the fresh air. But today, she encountered a particularly cunning butterfly — it flew into a labyrinth and tried to hide from her inside.

The labyrinth consists of $n$ rooms, numbered from $1$ to $n$ , some of which are connected by corridors. It is known that there is exactly one simple path between any two rooms, passing only through the corridors. In other words, the labyrinth forms a tree with $n$ vertices and $n - 1$ edges.

The entrance to the labyrinth is located in room number $1$ . A leaf is defined as any room connected to exactly one other room and not being the root (i.e., not room $1$ ). Each leaf contains an exit from the labyrinth. The butterfly starts its flight from room $1$ , heading toward one of the exits. It moves at a constant speed, never turns around, and travels through one corridor per minute, moving to a neighboring room. All corridors are of equal length.

To catch the butterfly, Nyusha decided to enlist the help of some friends. Initially, each of them can take position in any room that contains an exit. As soon as the butterfly begins its journey from the entrance toward some exit, the friends may immediately start moving from their rooms toward the entrance. They move at the same speed as the butterfly. If any of them encounters the butterfly — whether in a room or in the middle of a corridor — it is considered caught. However, if the butterfly reaches an exit without encountering any of the friends, it successfully escapes to freedom.

Help Nyusha determine the minimum number of friends needed to guarantee catching the butterfly, regardless of which exit it chooses.

Input. The first line contains a single integer $n (2 \leq n \leq 200000)$ — the number of rooms in the labyrinth.

The following $n - 1$ lines describe the corridors connecting the rooms. Each line contains two integers $u$ and $v (1 \leq u, v \leq n, u \neq = v)$ — the indices of the rooms connected by a corridor.

It is guaranteed that the given corridor system forms a tree.

Output. Print a single integer — the minimum number of friends required to guarantee that the butterfly will be caught.

Open problem

Perform a depth-first search starting from vertex $1$ . For each vertex, compute two values:

$d [v]$ — the distance from vertex $1$ to vertex $v$ . If $p$ is the parent of $v$ , then
$d [v] = d [p] + 1$
$h [v]$ — the distance from vertex v to the nearest leaf in the subtree rooted at $v$ . If $t o_{1}, t o_{2}, ..., t o_{k}$ are the children of vertex $v$ , then
$h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])$
If $v$ is a leaf of the tree, set $h [v] = 0$ .

Next, perform a second depth-first search. During this traversal, compute the value $res [v]$ — the minimum number of friends that need to be placed in some of the leaves of the subtree rooted at vertex $v$ in order to guarantee catching the butterfly, assuming it chooses to fly into this subtree.

If $h [v] \leq d [v]$ , then $res [v] = 1$ . In this case, it is enough to place one friend in the leaf with the minimal depth in the subtree rooted at vertex $v$ : they will reach vertex $v$ no later than the butterfly flying from the root.

Otherwise, if $t o_{1}, t o_{2}, ..., t o_{k}$ are the children of vertex $v$ , then

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

If the butterfly is not caught at vertex $v$ itself, we must be prepared to intercept it in any of the subtrees of $v$ 's children.

The final answer to the problem is the value $res [1]$ .

Example

In the first example (shown in the left diagram), two friends are required, and they should be placed at the two exits. The butterfly can fly from vertex $1$ either to vertex $2$ or to vertex $3$ . In either case, it will be intercepted by one of Nyusha's friends.

In the second example (shown in the right diagram), one friend is enough, who can be placed at either of the two exits — vertex $3$ or $4$ . The butterfly will fly from vertex $1$ to vertex $2$ in one minute. During that same time, the friend will reach vertex $2$ and catch the butterfly there.

Let us consider the next example.

Nyusha will need three friends to catch the butterfly.

Declare a constant for infinity and arrays.

#define INF 2000000000
vector<vector<int> > g;
vector<int> d, h, res;

The function dfs $(v, p, c n t)$ performs a depth-first search starting from vertex $v$ and returns the value $h [v]$ . Here, $p$ is the parent of vertex $v$ , and cnt is the distance from vertex $1$ to $v$ . During the traversal, the values $d [v]$ and $h [v]$ are computed for each vertex $v$ .

int dfs(int v, int p = -1, int cnt = 0)
{

The value $c n t$ , which equals the distance from vertex $1$ to $v$ , is stored in $d [v]$ .

  d[v] = cnt;
  int height = INF;

Iterate over all the children of the vertex $v$ . Consider the edge $v \to t o$ . If $t o$ equals the parent of $v (t o = p)$ , skip it and move to the next child.

  for (int to : g[v])
    if (to != p)

In the variable $h e i g h t$ compute the value

min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}]),

where $t o_{1}, t o_{2}, ..., t o_{k}$ are the children of vertex $v$ .

h e i g h t = min (h e i g h t, df s (t o, v, c n t + 1));

If $h e i g h t = I NF$ , then vertex $v$ is a leaf, and set $h [v] = 0$ . Otherwise rerturn

h [v] = 1 + min (h [t o_{1}], h [t o_{2}], ..., h [t o_{k}])

  return h[v] = (height == INF) ? 0 : 1 + height;
}

The function dfs2 $(v, p)$ performs a depth-first search starting from vertex $v$ and returns the value $res [v]$ . Here, $p$ is the parent of vertex $v$ .

int dfs2(int v, int p = -1)
{
  int s = 0;

Let $t o_{1}, t o_{2}, ..., t o_{k}$ be the children of vertex $v$ . In the variable $s$ , compute the sum:

res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}]

  for (int to : g[v])
    if (to != p)
    {
      dfs2(to, v);
      s += res[to];
    }

If $h [v] \leq d [v]$ , then one friend is sufficient, and $res [v] = 1$ . Otherwise

res [v] = res [t o_{1}] + res [t o_{2}] + ... + res [t o_{k}] = s

  return res[v] = (h[v] <= d[v]) ? 1 : s;
}

The main part of the program. Read the input data. Construct a graph.

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

Initialize the arrays.

d.resize(n + 1);
h.resize(n + 1);
res.resize(n + 1);

Run two depth-first searches. The first traversal computes the values of $d [v]$ and $h [v]$ for each vertex $v$ .

dfs(1);
dfs2(1);

Print the answer — the minimum number of friends needed to catch the butterfly.

printf("%lld\n", res[1]);

Kefa decided to celebrate his first big salary by going to a restaurant.

He lives near an unusual park. The park is a rooted tree with $n$ vertices, rooted at vertex $1$ . Kefa's house is located at vertex $1$ as well. Unfortunately for our hero, the park is inhabited by cats, and Kefa has already identified the vertices where the cats are located.

The leaf vertices of the park contain restaurants. Kefa wants to choose a restaurant, but he is very afraid of cats. Therefore, he will not go to a restaurant if, on the path from his house to the restaurant, he encounters more than $m$ consecutive vertices with cats.

Your task is to help Kefa count the number of restaurants he can safely visit.

Input. The first line contains two integers $n$ and $m (2 \leq n \leq 1 0^{5}, 1 \leq m \leq n)$ — the number of vertices in the tree and the maximum number of consecutive vertices with cats that Kefa can tolerate.

The second line contains $n$ integers $a_{1}, a_{2}, ..., a_{n}$ , where each $a_{i}$ is either $0$ (there is no cat at vertex $i$ ) or $1$ (there is a cat at vertex $i$ ).

The following $n - 1$ lines contains the tree's edges in the format $x_{i} y_{i} (1 \leq x_{i}, y_{i} \leq n, x_{i} \neq = y_{i})$ , where $x_{i}$ and $y_{i}$ are vertices connected by an edge.

It is guaranteed that this set of edges forms a tree.

Output. Print the number of leaf vertices that Kefa can reach if there are no more than $m$ consecutive vertices with cats on the way from his house.

Open problem

The location of the cats is stored in the array $c a t s$ . The tree is stored in the adjacency list $g$ .

vector<int> cats;
vector<vector<int> > g;

The dfs function performs a depth-first search from vertex $v$ and returns the number of restaurants that can be reached from this vertex (under the condition that no more than $m$ consecutive vertices with cats are encountered on the path to them). The parent of vertex $v$ is the vertex $p re v$ . The number of consecutive vertices with cats encountered up to and including vertex $v$ is $c n t$ .

int dfs(int v, int prev, int cnt)
{

If more than $m$ consecutive cats are already encountered, further depth-first search from vertex $v$ is not continued.

  if (cnt > m) return 0;

If we are at a leaf, increase the number of accessible restaurants.

  if (g[v].size() == 1 && prev != -1) return 1;

In the variable $res$ count the number of restaurants reachable from vertex $v$ .

  int res = 0;

Iterate over all edges $(v, t o)$ originating from vertex $v$ . If the vertex $t o$ is a parent of $v$ , do not move to this vertex.

  for (int to : g[v])
    if (to != prev) 
    {

If there is no cat at the vertex $v$ , set $c = 0$ . Otherwise, assign $c = c n t + 1$ . The variable $c$ stores the number of consecutive vertices with cats up to and including vertex $t o$ .

      int c = (cats[to] == 0) ? 0 : cnt + 1;

Start a depth-first search from vertex $t o$ .

      res += dfs(to, v, c);
    }

Return the result.

  return res;
}

The main part of the program. Read the input data.

scanf("%d %d", &n, &m);
cats.resize(n + 1);
for (i = 1; i <= n; i++)
  scanf("%d", &cats[i]);

Construct a tree.

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

Print the result. The dfs function, called from vertex $1$ , returns the answer to the problem. Since vertex $1$ has no parent, we pass the value $- 1$ as the second parameter. Starting from vertex $1$ , we have encountered $c a t s [1]$ cats.

printf("%d\n", dfs(1, -1, cats[1]));

Python implementation

def dfs(v, prev, cnt):

If more than $m$ consecutive cats are already encountered, further depth-first search from vertex $v$ is not continued.

  if cnt > m:
    return 0

If we are at a leaf, increase the number of accessible restaurants.

  if len(g[v]) == 1 and prev != -1:
    return 1

In the variable $res$ count the number of restaurants reachable from vertex $v$ .

  res = 0

Iterate over all edges $(v, t o)$ originating from vertex $v$ . If the vertex $t o$ is a parent of $v$ , do not move to this vertex.

  for to in g[v]:
    if to != prev:

If there is no cat at the vertex $v$ , set $c = 0$ . Otherwise, assign $c = c n t + 1$ . The variable $c$ stores the number of consecutive vertices with cats up to and including vertex $t o$ .

      c = 0 if cats[to] == 0 else cnt + 1

Start a depth-first search from vertex $t o$ .

      res += dfs(to, v, c)

Return the result.

  return res

The main part of the program. Read the input data.

n, m = map(int, input().split())
cats = [0] + list(map(int, input().split()))

Construct a tree.

g = [[] for _ in range(n + 1)]
for _ in range(n - 1):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)

print(dfs(1, -1, cats[1]))

The condition $d (i, j) = d (i, 1) - d (j, 1)$ holds for every pair of vertices $(i, j)$ where $j$ is an ancestor of $i$ in the depth-first search starting from vertex $1$ .

Let us consider an example:

$d (4, 1) = 2, d (4, 1) - d (1, 1) = 2 - 0 = 2$ ;
$d (6, 3) = 2, d (6, 1) - d (3, 1) = 3 - 1 = 2$ ;
$d (2, 2) = 0, d (2, 1) - d (2, 1) = 1 - 1 = 0;$
$d (6, 1) = 3, d (6, 1) - d (1, 1) = 3 - 0 = 3;$

Let us define the depth $h [v]$ of a vertex $v$ as the number of vertices on the path from the root (vertex $1$ ) to $v$ . In the diagram, the depth is written next to each vertex.

Now, fix a vertex $i$ and ask the question: how many vertices $j$ are there such that the condition $d (i, j) = d (i, 1) - d (j, 1)$ is satisfied?

For example, for $i = 6$ , there are $4$ such vertices: $j = 1, 3, 4, 6$ . Note that $h [6] = 4$ . Thus, for a fixed vertex $i$ , there are exactly $h [i]$ suitable vertices $j$ .

To solve the problem, we need to compute the depth $h [v]$ for each vertex $v$ in the tree, and then find the sum of all these depths across the tree.

Example

Let us consider the graph from the example. Next to each vertex, we write its depth.

The sum of the depths of all vertices is $1 + 2 + 3 + 3 + 4 = 13$ .

Define the graph's adjacency list as $g$ . The depths of the vertices are stored in the array $h$ .

vector<vector<int> > g;
vector<int> h;

The dfs function computes the depth of each vertex $v$ . The parent of vertex $v$ is the vertex $p$ .

int dfs(int v, int p)
{
  for (int to : g[v])

Consider the edge $(v, t o)$ . If the vertex $t o$ is not the parent of vertex $v$ , compute its depth and perform a depth first search starting from it.

    if (to != p)
    {
      h[to] = h[v] + 1;
      dfs(to, v);
    }
  return h[v];
}

The main part of the program. Read the number of vertices $n$ in the tree.

scanf("%d", &n);
g.resize(n + 1);

Construct a tree.

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

Set the depth of vertex $1$ to be $1$ .

h.resize(n + 1);
h[1] = 1;

Start a depth first search from the vertex $1$ .

dfs(1, -1);

Compute the answer — the sum of the depths of all vertices.

res = 0;
for (i = 1; i <= n; i++)
  res += h[i];

Print the answer.

printf("%lld\n", res);

You are given a binary tree, which is an acyclic connected undirected graph containing $n$ vertices and $n - 1$ edges. Each vertex has a degree of no more than $3$ . The root is the vertex number $1$ , with its degree not exceeding $2$ .

Unfortunately, the root of the tree is infected. The following process is repeated $n$ times:

Huseyn either selects a vertex that is not yet infected (and not yet removed) and removes it along with all its incident edges, or he takes no action.
After that, the infection spreads to every vertex connected by an edge to an already infected vertex (all previously infected vertices remain infected).

Help Huseyn determine the maximum number of vertices he can save from infection (note that removed vertices are not considered saved).

Input. The first line contains the number of vertices in the tree $n (2 \leq n \leq 3 \cdot 1 0^{5})$ .

Each of the following $n - 1$ lines contains two integers $u_{i}$ and $v_{i} (1 \leq u_{i}, v_{i} \leq n)$ , representing an edge of the tree.

It is guaranteed that the graph is a binary tree with the root at vertex $1$ .

Output. Print a single integer — the number of saved vertices.

Open problem

For each vertex $v$ , compute the number of vertices $s u m [v]$ in the subtree where it is the root. If $t o_{1}, t o_{2}, ..., t o_{k}$ are the children of vertex $v$ , then

s u m [v] = 1 + s u m [t o_{1}] + s u m [t o_{2}] + ... + s u m [t o_{k}]

If vertex $v$ is a leaf of the tree, then $s u m [v] = 1$ .

Let $d p [v]$ be the number of saved vertices in the subtree with root $v$ , assuming that currently vertex $v$ (and only it in the subtree) is infected.

If vertex $v$ has only one child $t o$ , then $d p [v] = s u m [t o] - 1$ (the removed vertex $t o$ is not considered saved).

Let vertex $v$ have two children $t o_{1}$ and $t o_{2}$ (each vertex has a degree of at most $3$ ). Then we have two options:

Remove $t o_{1}$ and recursively save the vertices in the subtree with root $t o_{2}$ . The number of saved vertices will be sum $s u m [t o_{1}] - 1 + d p [t o_{2}]$ .
Remove $t o_{2}$ and recursively save the vertices in the subtree with root $t o_{1}$ . The number of saved vertices will be $s u m [t o_{2}] - 1 + d p [t o_{1}]$ .

Among the two options, choose the one that maximizes the number of saved vertices.

Consider the depth-first search process when examining the edge $(v, t o)$ .

Let $a$ be the second child of vertex $v$ . We need to compute the value $d p [t o] + s u m [a] - 1$ . Let's try to find it using only the vertices $v$ and $t o$ . We know that:

s u m [v] = 1 + s u m [t o] + s u m [a]

From which it follows that:

s u m [a] = s u m [v] - s u m [t o] - 1

Thus,

d p [t o] + s u m [a] - 1 = d p [t o] + s u m [v] - s u m [t o] - 2

Iterate over the children $t o$ of the vertex $v$ and compute:

d p [v] = ma x (d p [t o] + s u m [v] - s u m [t o] - 2)

Example

In the first example, Huseyn is able to save two vertices, $3$ and $4$ , by choosing vertex number $2$ as his first move.|

Consider the second example. Next to each vertex $v$ , place the labels $s u m [v] / d p [v]$ . The vertices chosen by Huseyn are displayed in green.

For example,

d p [1] = ma x (s u m [2] - 1 + d p [5], s u m [5] - 1 + d p [2]) = ma x (2, 2) = 2, s u m [1] = 1 + s u m [2] + s u m [5] = 1 + 3 + 3 = 7

Declare the arrays.

#define MAX 300005
int sum[MAX], dp[MAX];
vector<vector<int>> g;

The function dfs performs a depth-first search starting from vertex $v$ . The parent of vertex $v$ is $p$ .

void dfs(int v, int p = -1)
{

Initialize the variables $s u m [v]$ and $d p [v]$ .

  sum[v] = 1;
  dp[v] = 0;

Perform a depth-first search starting from the children of vertex $v$ .

  for (int to : g[v])
    if (to != p)
    {
      dfs(to, v);
      sum[v] += sum[to];
    }

Compute the value of $d p [v]$ .

  for (int to : g[v])
    if (to != p)
    {
      dp[v] = max(dp[v], sum[to] - 1); // if 1 son
      dp[v] = max(dp[v], dp[to] + sum[v] - sum[to] - 2);
    }
}

The main part of the program. Read the input data.

scanf("%d", &n);
g.clear(); g.resize(n + 1);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Perform a depth-first search starting from vertex $1$ .

dfs(1);

Print the answer.

printf("%d\n", dp[1]);

List of problems

Comments (5)

user767927•25 days ago•2 revision

сайт розповідає з чого складається, як зробити

user897042•2 months ago

what a community i asked for help and noone cares.

user897042•2 months ago

https://codeforces.com/contest/315/problem/B how to solve this problem i wrote two updates one for assinging and second for interval with lazy. but it doesnt seem to work because two seperate updates doesnt have link between them.

medv•2 months ago

user897042 https://site.ada.edu.az/~medv/acm/Docs%20e-olimp/Volume%209/853_English.htm

user897042•2 months ago

user897042 need help on these two too:https://codeforces.com/contest/1857/problem/Ghttps://codeforces.com/contest/1702/problem/G

Loading

Just a moment, getting data from the server