PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: hyder1102
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Trees
PROBLEM:
Given a tree, count its dominating sets of size N-3.
EXPLANATION:
Rather than count dominating sets of size N-3, we’ll count non-dominating sets of size N-3, and subtract it from the total number of ways of choosing any subset of N-3 vertices.
Picking a subset of size N-3 is equivalent to picking a subset of size 3 (i.e. choosing which vertices to leave out), and so simply equals
Now we focus on counting non-dominating sets of size N-3.
For a subset to be non-dominating, there must exist a vertex x such that:
- x is not picked in the subset, and
- no neighbor of x is picked in the subset.
In particular, observe that if x has three or more neighbors, it will never satisfy this condition; since we leave out exactly three vertices.
So, the only x that matter are those with degree 1 or 2.
We analyze each one separately.
A degree 1 vertex is a leaf.
If we decide to not pick it, and also not pick its (unique) neighbor, then the subset is already non-dominating; so the third vertex we leave out can be any one of the remaining N-2.
Thus, for each leaf, we obtain N-2 non-dominating subsets.
Next, consider a degree 2 vertex.
Leaving out both it and its two neighbors gives a unique non-dominating subset of size N-3.
Finally, we need to worry about double counting.
This is not too hard, since we have only two cases.
First, we consider subsets that are counted in both cases.
Such a subset must contain both:
- A degree-2 vertex and its neighbors; and
- A leaf and its neighbor.
This is only possible when a degree-2 vertex has a leaf as its neighbor; and for each such degree-2 vertex there is exactly one such subset so we can just subtract 1 for each.
Next, we have the case where some subset was counted twice within the first case itself (i.e. leaf + unique neighbor + any other vertex.)
In this case, double counting can only happen if the third vertex chosen is also a leaf; and is adjacent to the unique neighbor of the first leaf.
In particular, for a vertex that has k leaves adjacent to it, every triple consisting of two of these leaves + the vertex itself, will be counted twice.
So, we subtract the number of such subsets, which is \frac{k\cdot (k-1)}{2}.
All of this can be done in linear time, since we only need to know which vertices are leaves, which have degree 2, and the count of leaves adjacent to each vertex.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
edges = []
for i in range(n-1):
u, v = map(int, input().split())
edges.append((u-1, v-1))
deg = [0]*n
for u, v in edges:
deg[u] += 1
deg[v] += 1
adjleaf = [0]*n
for u, v in edges:
if deg[u] == 1: adjleaf[v] += 1
if deg[v] == 1: adjleaf[u] += 1
ans = 0
for i in range(n):
if deg[i] == 1: ans += n-2
if deg[i] == 2:
ans += 1
if adjleaf[i]: ans -= 1
ans -= adjleaf[i]*(adjleaf[i]-1)//2
print(n*(n-1)*(n-2)//6 - ans)