The number of leaves and the height
A tree with n vertices (the root is 1) is given as n − 1 edges. Print the number of leaves and the height of the tree. (n ≥ 2)
Example
Input
8
1 2
1 3
1 4
2 5
2 6
4 7
7 8Output
4 3A tree is a connected graph without cycles. A family tree, the folder structure on a computer and the organisation of a school are trees. Because of their special shape, many tasks on trees are solved with a single traversal: depths, subtree sizes, the diameter.
A graph with n vertices is a tree if any of these holds (they are all equivalent): it is connected and has no cycle; it is connected and has exactly n − 1 edges; there is exactly one path between every two vertices.
1 depth 0
/ | \
2 3 4 depth 1
/ \ \
5 6 7 depth 2
\
8 depth 3
| Term | Meaning | In the example |
|---|---|---|
| root | the chosen starting vertex | 1 |
| parent, child | a neighbour closer to the root / farther from the root | the parent of vertex 6 is 2; the children of vertex 1 are 2, 3, 4 |
| leaf | a vertex without children | 3, 5, 6, 8 |
| depth | the number of edges from the root to the vertex | the depth of vertex 8 is 3 |
| height of the tree | the largest depth | 3 |
| subtree of vertex v | v and all the vertices below it | the subtree of vertex 2: {2, 5, 6} |
In the programs below this tree is entered as the number of vertices and then its n − 1 edges:
8
1 2
1 3
1 4
2 5
2 6
4 7
7 8
A tree is given as n − 1 edges. A depth-first traversal (DFS) from the root determines the parent and the depth of every vertex. Instead of a visited array it is enough not to go back to the parent – a tree has no other cycles.
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<int> parent, depth;
void dfs(int v, int p) { // p = the parent of vertex v
parent[v] = p;
for (int u : graph[v]) {
if (u == p) continue; // we do not go back
depth[u] = depth[v] + 1;
dfs(u, v);
}
}
int main() {
int n;
cin >> n;
graph.resize(n + 1);
parent.resize(n + 1);
depth.assign(n + 1, 0);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, 0); // the root is 1, its "parent" is 0
for (int v = 1; v <= n; v++)
cout << v << ": parent " << parent[v] << ", depth " << depth[v] << endl;
return 0;
}
For the tree from the picture the program prints:
1: parent 0, depth 0
2: parent 1, depth 1
3: parent 1, depth 1
4: parent 1, depth 1
5: parent 2, depth 2
6: parent 2, depth 2
7: parent 4, depth 2
8: parent 7, depth 3
The size of the subtree of vertex v is 1 (v itself) plus the sum of the sizes of its children's subtrees. The children are processed before the parent, so we calculate the size after the recursive calls (a postorder traversal).
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> graph;
vector<int> subtreeSize;
void dfs(int v, int p) {
subtreeSize[v] = 1; // vertex v itself
for (int u : graph[v]) {
if (u == p) continue;
dfs(u, v);
subtreeSize[v] += subtreeSize[u]; // add the child's subtree
}
}
int main() {
int n;
cin >> n;
graph.resize(n + 1);
subtreeSize.assign(n + 1, 0);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(1, 0);
for (int v = 1; v <= n; v++) cout << subtreeSize[v] << " ";
cout << endl;
return 0;
}
For the tree from the picture the program prints 8 3 1 3 1 1 2 1: for example, the subtree of vertex 4 is {4, 7, 8}.
The diameter is the largest distance (the number of edges) between two vertices of the tree. There is a nice trick with two traversals:
A;A find the farthest vertex B;A to B is the diameter.#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n;
vector<vector<int>> graph;
// BFS from vertex s; returns the distances of all the vertices from s
vector<int> bfs(int s) {
vector<int> d(n + 1, -1);
queue<int> q;
d[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int u : graph[v])
if (d[u] == -1) {
d[u] = d[v] + 1;
q.push(u);
}
}
return d;
}
int main() {
cin >> n;
graph.resize(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> d1 = bfs(1);
int A = 1;
for (int v = 1; v <= n; v++) if (d1[v] > d1[A]) A = v; // the farthest from 1
vector<int> d2 = bfs(A);
int B = A;
for (int v = 1; v <= n; v++) if (d2[v] > d2[B]) B = v; // the farthest from A
cout << "diameter = " << d2[B] << endl;
return 0;
}
In the example the diameter is the path 5 – 2 – 1 – 4 – 7 – 8 of length 5, so the program prints diameter = 5. BFS is used here instead of DFS to avoid deep recursion.
A tree is often given differently: for every vertex except the root its parent is given (p[2], p[3], …, p[n]). Then we build the graph by adding a child to every parent: children[p[v]].push_back(v). If p[v] < v always holds, the subtree sizes can also be calculated without recursion – by going from n back to 2: size[p[v]] += size[v].
Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.
A tree with n vertices (the root is 1) is given as n − 1 edges. Print the number of leaves and the height of the tree. (n ≥ 2)
8
1 2
1 3
1 4
2 5
2 6
4 7
7 84 3Every vertex of a tree has a value (it can also be negative). The root is 1. Print the largest sum of the values of some subtree.
Input: n, then n values, then n − 1 edges.
5
3 -10 4 2 2
1 2
1 3
2 4
2 54A tree and two vertices a and b are given. Print the number of edges on the path between them and the path itself.
Input: n, n − 1 edges, then a b.
8
1 2
1 3
1 4
2 5
2 6
4 7
7 8
5 85
5 2 1 4 7 8n − 1.long long.1. How many edges does a tree with 50 vertices have?
2. How many paths are there between two vertices of a tree?
3. When is the subtree size of vertex v calculated?
4. How is the diameter of a tree found?