Further analysis on the total number of subtrees of trees***Financially
supported by the National Natural Science Foundation of China (Grant No.
11071096) and the Special Fund for Basic Scientific Research of Central
Colleges (CCNU11A02015).

Shuchao Li†††E-mail<EMAIL_ADDRESS>(S.C. Li<EMAIL_ADDRESS>(S.J. Wang), Shujing Wang

Faculty of Mathematics and Statistics, Central China Normal University, Wuhan
430079, P.R. China

Abstract: We study that over some types of trees with a given number of
vertices, which trees minimize or maximize the total number of subtrees. Trees
minimizing (resp. maximizing) the total number of subtrees usually maximize
(resp. minimize) the Wiener index, and vice versa. Here are some of our
results: (1) Let $\mathscr{T}_{n}^{k}$ be the set of all $n$-vertex trees with
$k$ leaves, we determine the maximum (resp. minimum) value of the total number
of subtrees of trees among $\mathscr{T}_{n}^{k}$ and characterize the extremal
graphs. (2) Let $\mathscr{P}_{n}^{p,q}$ be the set of all $n$-vertex trees,
each of which has a $(p,q)$-bipartition, we determine the maximum (resp.
minimum) value of the total number of subtrees of trees among
$\mathscr{P}_{n}^{p,q}$ and characterize the extremal graphs. (3) Let
$\mathscr{A}_{n}^{q}$ be the set of all $q$-ary trees with $n$ non-leaf
vertices, we determine the minimum value of the total number of subtrees of
trees among $\mathscr{A}_{n}^{q}$ and identify the extremal graph.

Keywords: Subtrees; Leaves; Diameter; Bipartition; Wiener index; $q$-ary tree

AMS subject classification: 05C05, 05C10

##  1 Introduction

We consider only simple connected graphs (i.e. finite, undirected graphs
without loops or multiple edges). Let $G=(V_{G},E_{G})$ be a graph with
$u,v\in V_{G}$, $d_{G}(u)$ (or $d(u)$ for short) denotes the degree of $u$;
the distance $d_{G}(u,v)$ is defined as the length of the shortest path
between $u$ and $v$ in $G$; $D_{G}(v)$ denotes the sum of all distances from
$v$. The eccentricity $\varepsilon(v)$ of a vertex $v$ is the maximum distance
from $v$ to any other vertex.

Throughout the text we denote by $P_{n},\,K_{1,n-1}$ the path and star on $n$
vertices, respectively. $G-v,\,G-uv$ denote the graph obtained from $G$ by
deleting vertex $v\in V_{G}$, or edge $uv\in E_{G}$, respectively (this
notation is naturally extended if more than one vertex or edge is deleted).
Similarly, $G+uv$ is obtained from $G$ by adding vertex edge $uv\not\in
E_{G}$. For $v\in V_{G},$ let $N_{G}(v)$ (or $N(v)$ for short) denote the set
of all the adjacent vertices of $v$ in $G.$ The diameter diam$(G)$ of a graph
is the maximum eccentricity of any vertex in the graph. We refer to vertices
of degree 1 of a tree $T$ as leaves (or pendant vertices), and the edges
incident to leaves are called pendant edges. The unique path connecting two
vertices $v,u$ in $T$ will be denoted by $P_{T}(v,u)$. For a tree $T$ and two
vertices $v,u$ of $T$, the distance $d_{T}(v,u)$ between them counts the
number of edges on the path $P_{T}(v,u)$.

Let

$W(T)=\frac{1}{2}\sum_{v\in V_{T}}D_{T}(v)$

denote the Wiener index of $T,$ which is the sum of distances of all unordered
pairs of vertices. This topological index was introduced by Wiener [15], which
has been one of the most widely used descriptors in quantitative structure-
activity relationships. Since the majority of the chemical applications of the
Wiener index deal with chemical compounds with acyclic molecular graphs, the
Wiener index of trees has been extensively studied over the past years; see
[1, 2, 3, 4, 6] and the references there for details.

Given a tree $T$, a subtree of $T$ is just a connected induced subgraph of
$T$. The number of subtrees as well as related subjects has been studied. Let
$T$ denote a tree with $n$ nodes each of whose non-pendant vertices has degree
at least three, Andrew and Wang [12] showed that the average number of nodes
in the subtrees of $T$ is at least $\frac{n}{2}$ and strictly less than
$\frac{3n}{4}$. Székely and Wang [8] characterized the binary trees with $n$
leaves that have the greatest number of subtrees. Kirk and Wang [5] identified
the tree, for a given size and such that the vertex degree is bounded, having
the greatest number of subtrees. Székely and Wang [11] gave a formula for the
maximal number of subtrees a binary tree can possess over a given number of
vertices. They also show that caterpillar trees (trees containing a path such
that each vertex not belonging to the path is adjacent to a vertex on the
path) have the smallest number of subtrees among binary trees. Yan and Ye [16]
characterized the tree with the diameter at least $d$, which has the maximum
number of subtrees, and they characterized the tree with the maximum degree at
least $\Delta$, which has the minimum number of subtrees. For some related
results on the enumeration of subtrees of trees, one may also see Székely and
Wang [9, 10] and Wang [14]. Consider the collection of rooted labeled trees
with $n$ vertices, Song [7] derived a closed formula for the number of these
trees in which the child of the root with the smallest label has a total of
$p$ descendants. He also derived a recurrence relation for the number of these
trees with the property that for each non-terminal vertex $v$, the child of
$v$ with the smallest label has no descendants.

It is well known that the Wiener index is maximized by the path and minimized
by the star among general trees with the same number of vertices. It is also
known that the counterparts of these simple results for the number of subtrees
do exist. In fact, it is interesting that the Wiener index and the total
number of subtrees of a tree share exactly the same extremal structure (i.e.
the tree that maximizes/minimizes the corresponding index) among trees with a
given number of vertices and maximum degree, although the values of the
indices are in no general functional correspondence. On the other hand, an
acyclic molecule can be expressed by a tree in quantum chemistry (see [2]).
Obviously, the number of subtrees of a tree can be regarded as a topological
index. Hence, Yan and Ye [16] pointed out that to explore the role of the
total number of subtrees in quantum chemistry is an interesting topic.
Motivated by the work of [5, 8, 11, 12, 16], in this paper we continue to
study some types of trees which minimize or maximize the total number of
subtrees.

Let $\mathscr{T}_{n}^{k}$ be the set of all $n$-vertex trees with $k$ leaves
($2\leq k\leq n-1$). A spider is a tree with at most one vertex of degree more
than 2, called the center of the spider (if no vertex of degree more than two,
then any vertex can be the center). A leg of a spider is a path from the
center to a vertex of degree 1. Let $T_{n}^{k}$ be an $n$-vertex tree with $k$
legs satisfying all the lengths of $k$ legs, say $l_{1},l_{2},\ldots,l_{k}$,
are almost equal lengths, i.e., $|l_{i}-l_{j}|\leq 1$ for $1\leq i,j\leq k.$
It is easy to see that $T_{n}^{k}\in\mathscr{T}_{n}^{k}$ and
$l_{i}+l_{j}\in\\{2\lfloor\frac{n-1}{k}\rfloor,\lfloor\frac{n-1}{k}\rfloor+\lceil\frac{n-1}{k}\rceil,2\lceil\frac{n-1}{k}\rceil\\}$,
where $1\leq i,j\leq k.$ Let $P_{k}(a,b)$ be a tree obtained by attaching $a$
and $b$ pendant vertices to the two pendant vertices of $P_{k}$, respectively.
In particular, if $k=1$, then $P_{k}(a,b)=K_{1,a+b}$. It is straightforward to
check that
$P_{n-k}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)\in\mathscr{T}_{n}^{k}$.
It is known that the Wiener index among $n$-vertex trees with $k$ pendant
vertices is minimized by $T_{n}^{k}$ and is maximized by
$P_{n-k}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)$; see Dobrynin,
Entringer, Gutman [1]. We are going to show the counterparts of these results
for the number of subtrees, which also gives a confirm answer for a conjecture
proposed by Székely and Wang in [11].

######  Theorem 1.1.

Among ${\mathscr{T}}_{n}^{k}$ with $n\geq 2$.

  * (i)

Precisely the graph $T_{n}^{k}$, which has
$(\lfloor\frac{n-1}{k}\rfloor+1)^{i}(\lceil\frac{n-1}{k}\rceil+1)^{j}+i{\lfloor\frac{n-1}{k}\rfloor+1\choose{2}}+j{\lceil\frac{n-1}{k}\rceil+1\choose{2}}$
subtrees, maximizes the total number of subtrees among $\mathscr{T}_{n}^{k}$,
where $i+j=k$ and $n-1\equiv j\pmod{k}$.

  * (ii)

Precisely the graph
$P_{n-k}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)$, which has
$(2^{\lfloor\frac{k}{2}\rfloor}+2^{\lceil\frac{k}{2}\rceil})(n-k-1)+2^{k}+k+{n-k-1\choose{2}}$
subtrees, minimizes the total number of subtrees among $\mathscr{T}_{n}^{k}$.

Let $\mathscr{T}_{n,d}$ denote the set of all $n$-vertex trees of diameter
$d$. Let $\hat{T}_{n,k}^{d}$ be the $n$-vertex tree obtained from
$P_{d+1}=v_{1}v_{2}\ldots v_{d}v_{d+1}$ by attaching $n-d-1$ pendant edges to
$v_{k}$; see Fig. 1.

Figure 1: Tree $\hat{T}_{n,k}^{d}.$

######  Theorem 1.2.

For any $n\geq 2$, precisely the graph $\hat{T}_{n,i}^{d}$, which has

$2^{n-d-1}\left(\left\lfloor\frac{d}{2}\right\rfloor+1\right)\left(\left\lceil\frac{d}{2}\right\rceil+1\right)+{\lfloor\frac{d}{2}\rfloor+1\choose{2}}{\lceil\frac{d}{2}\rceil+1\choose{2}}+n-d-1$

subtrees, maximizes the total number of subtrees among $\mathscr{T}_{n,d}$,
where $i=\lfloor\frac{d}{2}\rfloor+1$ or $i=\lceil\frac{d}{2}\rceil+1$.

Let $G$ be a connected bipartite graph with $n$ vertices. Hence its vertex set
can be partitioned into two subsets $V_{1}$ and $V_{2}$, such that each edge
joins a vertex in $V_{1}$ with a vertex in $V_{2}$. Suppose that $V_{1}$ has
$p$ vertices and $V_{2}$ has $q$ vertices, where $p+q=n$. Then we say that $G$
has a $(p,q)$-bipartition $(p\leq q)$. Denote by $\mathscr{P}_{n}^{p,q}$ the
class of trees with $n$ vertices, each of which has a $(p,q)$-bipartition
$(p+q=n)$. Consider a star $K_{1,p}$ with $p+1$ vertices and attach $q-1$
pendant edges to a non-central vertex of the star $K_{1,p}$. The resulting
tree with $p+q$ vertices has a $(p,q)$-bipartition. Denote the resulting tree
by $D(p,q)$; see Fig. 2. Obviously, $D(p,q)\in\mathscr{P}_{n}^{p,q}$. We call
$D(p,q)$ a double star. If $q\geq p\geq 3$, suppose that $B(p,q)$ is the tree
obtained from $D(p-1,q)$ by attaching a pendant edge to one of the vertices of
degree one which join the vertex of degree $q$ in $D(p-1,q)$ (see Fig. 2). If
$q\geq p=2$, we assume that $B(2,q)$ is the tree obtained from the path
$P_{4}$ by attaching $q-2$ pendant edges to an end vertex of $P_{4}$ (see Fig.
2).

Figure 2: Trees $D(p,q),B(p,q)\,(p\geq q\geq 3)$ and $B(2,q).$

######  Theorem 1.3.

For any $n\geq 2$.

  * (i)

Precisely the graph $D(p,q)\ (q\geq p\geq 1)$, which has
$2^{n-2}+2^{p-1}+2^{q-1}+n-2$ subtrees, maximizes the total number of subtrees
among $\mathscr{P}_{n}^{p,q}$.

  * (ii)

Precisely the graph $B(p,q)\ (q\geq p\geq 2)$, which has

$3\cdot 2^{n-4}+3\cdot 2^{q-2}+2^{p-2}+n-1,$ if $p>2$ and $2^{n-2}+n+2$,
otherwise

subtrees, maximizes the total number of subtrees among
$\mathscr{P}_{n}^{p,q}\setminus\\{D(p,q)\\}.$

  * (iii)

Precisely the graph
$P_{2p-1}(\lfloor\frac{n-2p+1}{2}\rfloor,\lceil\frac{n-2p+1}{2}\rceil)$, which
has

$(2p-1)\left(2^{\lfloor\frac{n-2p+1}{2}\rfloor}+2^{\lceil\frac{n-2p+1}{2}\rceil}\right)+{n-2p+1\choose{2}}+2^{n-2p+1}+n-2p+1$

subtrees, minimizes the total number of subtrees among
$\mathscr{P}_{n}^{p,q}$.

Given positive integers $n,q$ with $q\geq 2$, we call $T$ a complete $q$-ary
tree (or $q$-ary tree for short) if any non-pendant vertex $v$ in $T$ has
exactly $q$ neighbours. Denote by $\mathscr{A}_{n}^{q}$ the class of $q$-ary
trees with $n$ non-leaf vertices ($(q-2)n+2$ leaves). Consider the path
$P_{n+2}$ and attach $q-2$ pendant edges to each of the non-leaf vertices of
$P_{n+2}$. Denote the resulting tree by $\hat{T}_{n}^{q}$ (see Fig. 3). It is
easy to see that $\hat{T}_{n}^{q}\in\mathscr{A}_{n}^{q}$. In view of Theorem
2.3 in [5], it is easy to determine the tree in $\mathscr{A}_{n}^{q}$ which
maximizes the total number of subtrees. It is natural and interesting to
determine the sharp lower bound on the total number of subtrees of trees among
$\mathscr{A}_{n}^{q}.$

Figure 3: Tree $\hat{T}_{n}^{q}.$

######  Theorem 1.4.

For $n\geq 1$, precisely the graph $\hat{T}_{n}^{q}$ (see Fig. 3), which has

$\frac{2^{q-2}(2^{q-1}-1)^{2}(2^{(n-1)(q-2)}-1)}{(2^{q-2}-1)^{2}}-\frac{n-1}{2^{q-2}-1}+2^{q}+nq-3n+3$

subtrees, minimizes the total number of subtrees among $\mathscr{A}_{n}^{q}.$

##  2 Some Lemmas

In this section, we give some necessary results which will be used to prove
our main results. For a set $S,$ let $|S|$ denote its cardinality. For two
graphs $G_{1},G_{2}$, if $G_{1}$ is a connected subgraph of $G_{2}$, then we
denote it by $G_{1}\subseteq G_{2}$. Given a tree $T$ with $u,\,v\in V_{T}$,
let

$\begin{array}[]{ll}\ \ \ f_{T}(u)=|\\{T^{\prime}:\ \ T^{\prime}\subseteq
T,\,u\in V_{T^{\prime}}\\}|,&f_{T}(u*v)=|\\{T^{\prime}:\ \ T^{\prime}\subseteq
T,\,u,\,v\in V_{T^{\prime}}\\}|,\\\ f_{T}(u/v)=|\\{T^{\prime}:\ \
T^{\prime}\subseteq T,\,u\in V_{T^{\prime}},v\not\in V_{T^{\prime}}\\}|,&\ \ \
\ \ F(T)=|\\{T^{\prime}:\,T^{\prime}\subseteq T,\,|V_{T^{\prime}}|\geq
1\\}|.\end{array}$

######  Lemma 2.1 ([11]).

The $n$-vertex path $P_{n}$ has ${{n+1}\choose{2}}$ subtrees, fewer than any
other tree on n vertices.

Figure 4: Path $P_{W}(x,y)$ connecting vertices $x$ and $y$.

Consider the tree $W$ in Fig. 4 with vertices $x$ and $y$, and

$P_{W}(x,y)=x_{0}(x)x_{1}\ldots x_{n}zy_{n}\ldots
y_{1}y_{0}(y)(x_{0}(x)x_{1}\ldots x_{n}y_{n}\ldots y_{1}y_{0}(y))$

if $d_{W}(x,y)$ is even (odd) for any $n\geq 0$. After the deletion of all the
edges of $P_{W}(x,y)$ from $W$, some connected components will remain. Let
$X_{i}(X_{0})$ denote the component that contains $x_{i}(x_{0}=x)$, let
$Y_{i}(Y_{0})$ denote the component that contains $y_{i}(y_{0}=y)$, for
$i=1,2,\ldots,n$, and let $Z$ denote the component that contains $z$.

######  Lemma 2.2 ([8]).

In the above situation, if $f_{X_{i}}(x_{i})\geq f_{Y_{i}}(y_{i})$ for
$i=0,1,\ldots,n$, then $f_{W}(x)\geq f_{W}(y)$. Furthermore,
$f_{W}(x)=f_{W}(y)$ if and only if $f_{X_{i}}(x_{i})=f_{Y_{i}}(y_{i})$ for all
$i$.

If we have a tree $T$ with vertices $x$ and $y$, and two rooted trees $X$ and
$Y$, then we can build two new trees, first $T^{\prime}$, by identifying the
root of $X$ with $x$ and the root of $Y$ with $y$, second $T^{\prime\prime}$,
by identifying the root of $X$ with $y$ and the root of $Y$ with $x$ (as shown
in Fig. 5).

Figure 5: Switching subtrees rooted at $x$ and $y$.

######  Lemma 2.3 ([8]).

In the above situation, if $f_{T}(x)>f_{T}(y),f_{X}(x)<f_{Y}(y)$, then we have
$F(T^{\prime\prime})>F(T^{\prime})$.

######  Corollary 2.4.

In the above situation, if $f_{T}(x)>f_{T}(y)$ and $X$ is a rooted tree that
is not a single vertex, then we have $F(T^{\prime\prime})>F(T^{\prime})$,
where $T^{\prime}$ (resp. $T^{\prime\prime}$) is obtained by identifying the
root of $X$ with $y$ (resp. $x$) of $T$.

######  Lemma 2.5.

Given an $n$-vertex path $P_{n}=v_{1}v_{2}\ldots v_{n}$, one has
$f_{P_{n}}(v_{k})=k(n-k+1)$ for $k\in\\{1,2,\ldots,n\\}$. Furthermore, one has

$\begin{split}f_{P_{n}}(v_{k})&=f_{P_{n}}(v_{n-k+1}),\\\
f_{P_{n}}(v_{1})<f_{P_{n}}(v_{2})<\cdots<f_{P_{n}}(v_{k})&<f_{P_{n}}(v_{k+1})<\cdots<f_{P_{n}}(v_{\lfloor\frac{n+1}{2}\rfloor})=f_{P_{n}}(v_{\lceil\frac{n+1}{2}\rceil}).\end{split}$
(2.1)

###### Proof.

For any $P\subseteq P_{n}$ such that $P$ contains $v_{k}$, it can be denoted
by $P=v_{i}v_{i+1}\ldots v_{k}\ldots v_{j}$, where $i\leq k\leq j$. It is easy
to see that we have $i\in\\{1,2,\ldots,k\\}$ and $j\in\\{k,k+1,\ldots,n\\}.$
Hence, we have $f_{P_{n}}(v_{k})=k(n-k+1)$.

Consider the function $f(x)=x(n-x+1)$ for $x\geq 0$. By the monotonicity of
$f(x)$, we have

$f(k)=f(n-k+1),\ \ \ \
f(1)<f(2)<\cdots<f(k)<f(k+1)<\cdots<f(\left\lfloor\frac{n+1}{2}\right\rfloor)=f(\left\lceil\frac{n+1}{2}\right\rceil),$

which is equivalent to (2.1), as desired. ∎

By Corollary 2.4 and Lemma 2.5, the following lemma follows immediately.

######  Lemma 2.6.

Given a tree $T$ with at least two vertices and a path $P_{k}=v_{1}v_{2}\ldots
v_{k}$, let $T_{i}$ be a tree obtained from $T$ and $P_{k}$ by identifying a
vertex $v$ of $T$ with $v_{i}$ of $P_{k}$,
$i\in\\{2,3,\ldots,\lfloor\frac{k+1}{2}\rfloor-2\\}$. Then we have

$F(T_{i})=F(T_{k-i+1})$

and

$F(T_{1})<F(T_{2})<\cdots<F(T_{i})<\cdots<F(T_{\lfloor\frac{k+1}{2}\rfloor}).$

######  Lemma 2.7.

Given a tree $T$ with $uv\in E_{T}$ and $u$ is a leaf, one has $f_{T}(u)\leq
f_{T}(v)$, with equality if and only if $T\cong K_{2}$.

###### Proof.

For any edge $uv$ in $E_{T}$, we have

$f_{T}(u)=f_{T}(u*v)+f_{T}(u/v),\ \ \ \ f_{T}(v)=f_{T}(u*v)+f_{T}(v/u).$ (2.2)

In particular, if $u$ is a leaf and $uv\in E_{T}$, then we have
$f_{T}(u/v)=1,\,f_{T}(v/u)=f_{T-u}(v)\geq 1,$ with equality if and only if
$T-u$ is a single vertex, i.e., $T\cong K_{2}$. Our result holds immediately.
∎

######  Lemma 2.8.

Given a tree $T$ with $u,v\in V_{T}$ satisfying $f_{T}(u)\leq f_{T}(v),$ let
$T^{\prime}$ be a tree obtained from $T$ by adding a new vertex $v_{s}$ to
some vertex of $T$ such that in $T^{\prime}$ the unique path between $u$ and
$v_{s}$ contains $v,$ then $f_{T^{\prime}}(u)<f_{T^{\prime}}(v)$.

###### Proof.

Note that $f_{T}(u)\leq f_{T}(v)$, hence in view of (2.2), we have
$f_{T}(u/v)\leq f_{T}(v/u)$. By the structure of $T^{\prime}$, it is
straightforward to check that $f_{T^{\prime}}(u/v)=f_{T}(u/v)$, and
$f_{T^{\prime}}(v/u)>f_{T}(v/u)$, hence we have

$f_{T^{\prime}}(u)=f_{T^{\prime}}(u*v)+f_{T^{\prime}}(u/v)<f_{T^{\prime}}(v*u)+f_{T^{\prime}}(v/u)=f_{T^{\prime}}(v),$

as desired. ∎

######  Lemma 2.9.

Let $P=uu_{1}\ldots v_{1}v$ be a path of a tree $T$ with
$N_{T}(u)=\\{u_{1},w,w_{1},\ldots,w_{s}\\}$,
$N_{T}(v)=\\{v_{1},z,z_{1},\ldots,z_{t}\\}$, here $s\geq 1,t\geq 1$. Then
$F(T)<F(T^{\prime})$ or $F(T)<F(T^{\prime\prime})$, where

$\displaystyle T^{\prime}$ $\displaystyle=$ $\displaystyle
T-uw_{1}-uw_{2}-\cdots-uw_{s}+vw_{1}+vw_{2}+\cdots+uw_{s},$ $\displaystyle
T^{\prime\prime}$ $\displaystyle=$ $\displaystyle T-vz_{1}-vz_{2}-\cdots-
vz_{t}+uz_{1}+uz_{2}+\cdots+uz_{t}.$

###### Proof.

Consider the component in $T-uw_{1}-uw_{2}-\cdots-uw_{s}-vz_{1}-vz_{2}-\cdots-
vz_{t}$, say $\hat{T}$, which contains both $u$ and $v$. If
$f_{\hat{T}}(u)\leq f_{\hat{T}}(v)$, then by Lemma 2.8, we have

$f_{\tilde{T}}(u)<f_{\tilde{T}}(v),$

where $\tilde{T}$ is just the component containing both $u$ and $v$ in the
graph $T-uw_{1}-uw_{2}-\cdots-uw_{s}.$ By Corollary 2.4, we have
$F(T)<F(T^{\prime})$.

If $f_{\hat{T}}(v)<f_{\hat{T}}(u)$, similarly we can also show that
$F(T)<F(T^{\prime\prime})$. We omit the procedure here.

This completes the proof. ∎

######  Lemma 2.10.

Given a tree $T$ containing a path $P_{r}=v_{1}v_{2}\ldots v_{r},$ there
exists a vertex $v_{i}\in V_{P_{r}}\setminus\\{v_{1},v_{r}\\}$ such that

$f_{T}(v_{1})<\cdots<f_{T}(v_{i-1})<f_{T}(v_{i})\geq
f_{T}(v_{i+1})>\cdots>f_{T}(v_{r}).$ (2.3)

###### Proof.

Consider three vertices $x,y,z$ such that $xy,yz\in E_{T}$. Let $X,Y,Z$,
respectively, denote the components containing $x,y,z$ after the removal of
the edges $xy$ and $yz$ from $T$. Observe the identities

$\displaystyle f_{T}(x)$ $\displaystyle=$ $\displaystyle
f_{X}(x)+f_{X}(x)f_{Y}(y)+f_{X}(x)f_{Y}(y)f_{Z}(z),$ $\displaystyle f_{T}(z)$
$\displaystyle=$ $\displaystyle
f_{Z}(z)+f_{Z}(z)f_{Y}(y)+f_{Z}(z)f_{Y}(y)f_{X}(x),$ $\displaystyle f_{T}(y)$
$\displaystyle=$ $\displaystyle
f_{Y}(y)+f_{X}(x)f_{Y}(y)+f_{Z}(z)f_{Y}(y)+f_{X}(x)f_{Y}(y)f_{Z}(z).$

This gives

$2f_{T}(y)-f_{T}(x)-f_{T}(z)=2f_{Y}(y)+(f_{X}(x)+f_{Z}(z))(f_{Y}(y)-1)>0.$
(2.4)

Let

$i=\min\\{j:\ 1\leq j\leq r,\,f_{T}(v_{j})\geq f_{T}(u),\,u\in V_{P_{r}}\\}.$

by Lemma 2.7, $i\not=1,r.$ Hence, we have

$f_{T}(v_{i})\geq f_{T}(v_{i+1}),\ \ \ f_{T}(v_{i})>f_{T}(v_{i-1}).$

Next consider three consecutive vertices $v_{i},v_{i+1},v_{i+2}$ on $P_{r},$
in view of (2.4) we have

$2f_{T}(v_{i+1})-f_{T}(v_{i})-f_{T}(v_{i+2})>0.$

Combining with $f_{T}(v_{i})\geq f_{T}(v_{i+1})$ yields

$f_{T}(v_{i})\geq f_{T}(v_{i+1})>f_{T}(v_{i+2}).$

Repeated as above we obtain

$f_{T}(v_{i})\geq f_{T}(v_{i+1})>\cdots>f_{T}(v_{r}).$ (2.5)

Similarly, we obtain

$f_{T}(v_{1})<\cdots<f_{T}(v_{i-1})<f_{T}(v_{i}).$ (2.6)

Hence, (2.5) and (2.6) imply (2.3) immediately. ∎

##  3 Proof of Theorem 1.1

In this section, we shall determine sharp upper and lower bounds on the total
number of subtrees of $n$-vertex tree with $k$ pendants.

Proof of Theorem 1.1. (i) First we enumerate the total number of subtrees of
$T_{n}^{k}$. Consider the unique vertex, say $v_{0}$, the center of
$T_{n}^{k}$ whose degree is $k$, we have

$\displaystyle
F(T_{n}^{k})=f_{T_{n}^{k}}(v_{0})+F(T-v_{0})=f_{T_{n}^{k}}(v_{0})+F(iP_{\lfloor\frac{n-1}{k}\rfloor}\cup
jP_{\lceil\frac{n-1}{k}\rceil}),$ (3.1)

where $i+j=k$ and $n-1\equiv j\pmod{k}$. On the one hand,

$f_{T_{n}^{k}}(v_{0})=\left(\left\lfloor\frac{n-1}{k}\right\rfloor+1\right)^{i}\left(\left\lceil\frac{n-1}{k}\right\rceil+1\right)^{j}.$

On the other hand, by Lemma 2.1 we have

$F(iP_{\lfloor\frac{n-1}{k}\rfloor}\cup
jP_{\lceil\frac{n-1}{k}\rceil})=i{\lfloor\frac{n-1}{k}\rfloor+1\choose{2}}+j{\lceil\frac{n-1}{k}\rceil+1\choose{2}},$

where $i+j=k$ and $j\equiv n-1\pmod{k}$. Together with (3.1), we have

$F(T_{n}^{k})=\left(\left\lfloor\frac{n-1}{k}\right\rfloor+1\right)^{i}\left(\left\lceil\frac{n-1}{k}\right\rceil+1\right)^{j}+i{\lfloor\frac{n-1}{k}\rfloor+1\choose{2}}+j{\lceil\frac{n-1}{k}\rceil+1\choose{2}},$

as desired.

Now we show that $T_{n}^{k}$ is the unique graph which maximizes the total
number of subtrees among $\mathscr{T}_{n}^{k}.$ Choose
$T\in\mathscr{T}_{n}^{k}$ such that the total number of its subtrees is as
large as possible.

If $k=2$ or, $k=n-1$, it is easy to see that
$\mathscr{T}_{n}^{k}=\\{T_{n}^{k}\\}$, our result follows immediately. Hence,
in what follows we consider $2<k<n-1$.

We are to show that $T$ is a spider, i.e., $T$ contains a unique vertex of
degree larger than 2. Assume to the contrary that $T$ contains at least $2$
vertices of degree greater than 2. By Lemma 2.9, there exists an $n$-vertex
tree $T^{\prime}\in\mathscr{T}_{n}^{k}$ such that $F(T)<F(T^{\prime})$, a
contradiction to the choice of $T$. Hence, we assume that $v_{0}$ is the
unique vertex of degree greater than 2.

In order to complete the proof, it suffices to show that all the legs attached
to $v_{0}$ of $T$ are almost equal lengths. Let
$PV(T)=\\{u_{1},u_{2},\ldots,u_{k}\\}$ be the set of all pendant vertices of
$T$. We are to show that for any $u_{i},u_{j}\in PV(T)$, we have
$|d_{T}(v_{0},u_{i})-d_{T}(v_{0},u_{j})|\leq 1.$ Assume to the contrary that
there exist two pendant vertices, say $u_{t},u_{l}$, in $PV(T)$ such that

$|d_{T}(u_{0},u_{t})-d_{T}(u_{0},u_{l})|\geq 2.$ (3.2)

Denote the unique path connecting $u_{t}$ and $u_{l}$ by
$P_{s}=w_{1}w_{2}\ldots w_{i-1}w_{i}w_{i+1}\ldots w_{s},$ where
$w_{1}=u_{t},w_{s}=u_{l}$ and $w_{i}=u_{0},1\leq i\leq s$. In view of (3.2),
we have

$\text{$u_{0}=w_{i}\neq w_{\lfloor\frac{s+1}{2}\rfloor}$\ \ \ and\ \ \
$u_{0}=w_{i}\neq w_{\lceil\frac{s+1}{2}\rceil}$}.$

Hence, by Lemma 2.6 there exists an $n$-vertex tree
$T^{\prime\prime}\in\mathscr{T}_{n}^{k}$ such that $F(T)<F(T^{\prime\prime})$,
a contradiction to the choice of $T$.

This completes the proof of Theorem 1.1(i).

(ii) If $k=2$ or, $k=n-1$, it is easy to see that
$\mathscr{T}_{n}^{k}=\\{P_{n-k-1}(\lfloor\frac{k}{2}\rfloor,\lceil\frac{k}{2}\rceil)\\}$,
our result follows immediately. Hence, in what follows we consider $2<k<n-1$.
In order to complete the proof, it suffices to show the following claims.

######  Claim 1.

If $T$ minimizes the total number of subtrees in $\mathscr{T}_{n}^{k},T\cong
P_{n-k}(a,b)$, where $a\geq b\geq 1$ and $a+b=k$.

Proof of Claim 1 If diam$(T)=3$, the claim follows immediately. Hence we
consider the trees whose diameter is larger than 3. Suppose that
$P_{r}=v_{1}\ldots v_{r}(r\geq 5)$ is one of the longest path in $T$, we are
to show that $d_{T}(v_{3})=d_{T}(v_{4})=\cdots=d_{T}(v_{r-2})=2$. Assume to
the contrary that there exists $v\in\\{v_{3},v_{4},\ldots,v_{r-2}\\}$ such
that $d_{T}(v)\geq 3.$ Let

$i=\min\\{j:\ d_{T}(v_{j})\geq 3,\ \ \ 3\leq j\leq r-2\\},\ \ \ \
N_{T}(v_{i})=\\{v_{i-1},v_{i+1},z_{1},z_{2},\ldots,z_{s}\\},\ \ s\geq 1.$

After the deletion of all the vertices $z_{1},z_{2},\ldots,z_{s}$ from $T$,
let $T_{0}$ denote the component containing $v_{i}$. By Lemma 2.10, there
exists $v_{t}\in V_{P_{r}}$ such that

$f_{T_{0}}(v_{1})<\cdots<f_{T_{0}}(v_{t-1})<f_{T_{0}}(v_{t})\geq
f_{T_{0}}(v_{t+1})>\cdots>f_{T_{0}}(v_{r}).$

If $t<i,$ then we have $f_{T_{0}}(v_{i})>f_{T_{0}}(v_{r-1})$. By Corollary
2.4, we have

$F(T)>F(T^{\prime}),$ (3.3)

where

$T^{\prime}=T-v_{i}z_{1}-\cdots-v_{i}z_{s}+v_{r-1}z_{1}+\cdots+v_{r-1}z_{s}.$

If $t\geq i,$ then we have $f_{T_{0}}(v_{i})>f_{T_{0}}(v_{2})$. By Corollary
2.4, we have

$F(T)>F(T^{\prime\prime}),$ (3.4)

where

$T^{\prime\prime}=T-v_{i}z_{1}-\cdots-
v_{i}z_{s}+v_{2}z_{1}+\cdots+v_{2}z_{s}.$

It is easy to see that $T^{\prime},\,T^{\prime\prime}\in\mathscr{T}_{n}^{k}.$
Hence, (3.3) (resp. (3.4)) is a contradiction to the choice of $T$. This
completes the proof of Claim 1. ∎

######  Claim 2.

For positive integers $a,b$ with $a\geq b$ and $a+b=k$ one has

$F(P_{n-k}(a,b))=(2^{a}+2^{b})(n-k-1)+2^{k}+k+{n-k-1\choose{2}}$ (3.5)

and if $a-b\geq 2$, then

$F(P_{n-k}(a,b))>F(P_{n-k}(a-1,b+1)).$ (3.6)

Proof of Claim 2 For convenience, assume that $d_{P_{n-k}(a,b)}(v_{1})=a$ and
$d_{P_{n-k}(a,b)}(v_{n-k})=b$. Then we have

$\begin{split}F(P_{n-k}(a,b))=&f_{P_{n-k}(a,b)}(v_{1}/v_{n-k})+f_{P_{n-k}(a,b)}(v_{1}*v_{n-k})+f_{P_{n-k}(a,b)}(v_{n-k}/v_{1})\\\
&+F(P_{n-k}(a,b)-v_{1}-v_{n-k}).\end{split}$ (3.7)

By direct calculation, we have

$f_{P_{n-k}(a,b)}(v_{1}/v_{n-k})=2^{a}(n-k-1)$ and
$f_{P_{n-k}(a,b)}(v_{n-k}/v_{1})=2^{b}(n-k-1)$. (3.8)

It is straightforward to check that the total number of subtrees of
$P_{n-k}(a,b)$ containing both $v_{1}$ and $v_{n-k}$ is equal to the total
number of subtrees of $K_{1,a+b}$ each contains the center of $K_{1,a+b}$.
Hence, we have

$f_{P_{n-k}(a,b)}(v_{1}*v_{n-k})=2^{a+b}=2^{k}.$ (3.9)

On the other hand,

$F(P_{n-k}(a,b)-v_{1}-v_{n-k})=F((a+b)P_{1}\cup
P_{n-k-2})=k+{n-k-1\choose{2}}.$ (3.10)

In view of (3.7)-(3.10), (3.5) holds.

By (3.5), we have

$F(P_{n-k}(a,b))-F(P_{n-k}(a-1,b+1))=(2^{a}+2^{b}-2^{a-1}-2^{b+1})(n-k-1)=(2^{a-1}-2^{b})(n-k-1).$

Note that $a-b\geq 2$, hence $(2^{a-1}-2^{b})(n-k-1)>0$, i.e.,
$F(P_{n-k}(a,b))>F(P_{n-k}(a-1,b+1))$, as desired. ∎

By Claims 1 and 2, Theorem 1.1(ii) follows immediately.∎

##  4 Proof of Theorem 1.2

Proof of Theorem 1.2 In view of Theorem 3.7 in [16], we know that
$\hat{T}_{n,i}^{d}$,
$i=\lfloor\frac{d+2}{2}\rfloor=\lfloor\frac{d}{2}\rfloor+1$ or
$i=\lceil\frac{d+2}{2}\rceil=\lceil\frac{d}{2}\rceil+1$, is the unique graph
maximizing the total number of subtrees among $\mathscr{T}_{n,d}$. In order to
complete the proof, it suffices to show that

$F(\hat{T}_{n,i}^{d})=2^{n-d-1}\left(\left\lfloor\frac{d}{2}\right\rfloor+1\right)\left(\left\lceil\frac{d}{2}\right\rceil+1\right)+{\lfloor\frac{d}{2}\rfloor+1\choose{2}}{\lceil\frac{d}{2}\rceil+1\choose{2}}+n-d-1,$
(4.1)

where $i=\lfloor\frac{d}{2}\rfloor+1$ or $i=\lceil\frac{d}{2}\rceil+1$.

In fact, it is easy to see that

$F(\hat{T}_{n,i}^{d})=f_{\hat{T}_{n,i}^{d}}(x)+F(\hat{T}_{n,i}^{d}-x)$ (4.2)

for any $x\in V_{\hat{T}_{n,i}^{d}}$.

Without loss of generality, consider $x:=v_{\lfloor\frac{d}{2}\rfloor+1}$
whose neighbor contains just $n-d-1$ leaves. By Lemma 2.5, we have

$f_{P_{d+1}}(x)=\left(\left\lfloor\frac{d}{2}\right\rfloor+1\right)\left(d+1+1-(\left\lfloor\frac{d}{2}\right\rfloor+1)\right)=\left(\left\lfloor\frac{d}{2}\right\rfloor+1\right)\left(\left\lceil\frac{d}{2}\right\rceil+1\right)$

which leads to

$f_{\hat{T}_{n,i}^{d}}(x)=2^{n-d-1}\left(\left\lfloor\frac{d}{2}\right\rfloor+1\right)\left(\left\lceil\frac{d}{2}\right\rceil+1\right).$
(4.3)

On the other hand,

$\hat{T}_{n,i}^{d}-x=(n-d-1)P_{1}\cup P_{\lfloor\frac{d}{2}\rfloor}\cup
P_{\lceil\frac{d}{2}\rceil}.$

By Lemma 2.1, we have

$F(\hat{T}_{n,i}^{d}-x)=n-d-1+{{\lfloor\frac{d}{2}\rfloor}+1\choose{2}}{{\lceil\frac{d}{2}\rceil}+1\choose{2}}.$
(4.4)

In view of Eqs. (4.2)-(4.4), Eq. (4.1) follows immediately. ∎

##  5 Proof of Theorem 1.3

In this section, we prove Theorem 1.3. For convenience, denote by $\iota(T)$
the number of non-pendant vertices in $T$.

Proof Theorem 1.3 (i) First we show that $D(p,q)$ is the tree in
$\mathscr{P}_{n}^{p,q}$ which has the largest number of subtrees. For any
$T\in\mathscr{P}_{n}^{p,q}$. If $p=1$,
$\mathscr{P}_{n}^{p,q}=\\{K_{1,n-1}\\}=\\{D(1,n-1)\\}$. Our result holds in
this case. Hence, in what follows, we consider $p\geq 2.$ In order to
determine the structure of the extremal graph, say $T$, in this case, it
suffice to show that $\iota(T)=2.$

Hence, we assume to the contrary that $\iota(T)\geq 3.$

Choose three vertices, say $u,v,w$, such that each of them is of degree at
least 3. Let $V_{T}=V_{1}\cup V_{2}$. It is straightforward to check that in
$\\{u,v,w\\}$, there exist two elements are in $V_{1}$ or $V_{2}$. We assume,
without loss of generality, that $u,v\in V_{1}$ with
$N_{T}(u)=\\{u_{1},z_{1},\ldots,z_{t}\\},N_{T}(v)=\\{u_{2k-1},r_{1},\ldots,r_{s}\\}$,
$t\geq 1,s\geq 1$ and the unique path joining $u$ and $v$ is $P=uu_{1}\ldots
u_{2k-1}v$. Let $X_{u}$ be the component that contains $u$ in $T-E_{P}$ and
$Y_{v}$ the component that contains $v$ in $T-E_{P}$. Let $T^{\prime}$ be the
component that contains $u$ in $T-uz_{1}-\cdots-uz_{t}-vr_{1}-\cdots-vr_{s}$.

If $f_{T^{\prime}}(u)\geq f_{T^{\prime}}(v)$, by Lemma 2.8 we have

$f_{T^{\prime\prime}}(u)>f_{T^{\prime\prime}}(v),$ (5.1)

where $T^{\prime\prime}$ is obtained by identifying $u$ of $T^{\prime}$ with
$u$ of $X_{u}$. Let $T^{*}$ be the tree obtained by identifying $u$ of
$T^{\prime\prime}$ with $v$ of $Y_{v}$. Note that $u$ and $v$ are in $V_{1}$,
hence we have $T^{*}\in\mathscr{P}_{n}^{p,q}$. On the other hand, notice that
$Y_{v}$ is not a single vertex, together with (5.1) and Corollary 2.4, we have
$F(T)<F(T^{*})$, a contradiction to the choice of $T$.

Similarly, if $f_{T^{\prime}}(u)<f_{T^{\prime}}(v)$, we can also show there
exists a tree $\hat{T}\in\mathscr{P}_{n}^{p,q}$ such that $F(T)<F(\hat{T})$, a
contradiction. We omit the procedure here. Hence, we get that $\iota(T)=2$,
i.e., $T\cong D(p,q),$ as desired.

Now we show that

$\displaystyle F(D(p,q))=2^{n-2}+2^{p-1}+2^{q-1}+n-2.$ (5.2)

In fact, let $d_{D(p,q)}(u)=p$ and $d_{D(p,q)}(v)=q$, we have

$F(D(p,q)=f_{D(p,q)}(u/v)+f_{D(p,q)}(u*v)+f_{D(p,q)}(v/u)+F(D(p,q)-v-u).$

It is easy to see that $f_{D(p,q)}(u/v)=2^{p-1},f_{D(p,q)}(v/u)=2^{q-1}$ and
any subtree that contains both $u$ and $v$ can be considered be the subtree
that contains the center of $K_{1,n-2}$, so we have $f_{D(p,q)}(u*v)=2^{n-2}$.
On the other hand, as

$F(D(p,q)-v-u)=F((p-1)P_{1}\cup(q-1)P_{1})=n-2$

Therefore, Eq.(5.2) holds. This completes the proof of Theorem 1.3 (i).

(ii) Suppose $T^{\prime}$ is the tree in
$\mathscr{P}_{n}^{p,q}\setminus\\{D(p,q)\\}$ with $q\geq p\geq 2$ which has
the largest number of subtrees. First we show that $\iota(T^{\prime})=3$. Note
that $T^{\prime}\not\cong D(p,q)$, we know that $\iota(T)\neq 1,2$. If
$\iota(T^{\prime})>3$, then by a similar discussion as in the proof of Theorem
1.3 (i), there exists a tree $T^{\prime\prime}\in\mathscr{P}_{n}^{p,q}$ such
that $\iota(T^{\prime\prime})=\iota(T^{\prime})-1\geq 3$ and
$F(T^{\prime})<F(T^{\prime\prime})$. Note that $\iota(T^{\prime\prime})\geq
3$, hence $T^{\prime\prime}\in\mathscr{P}_{n}^{p,q}\setminus\\{D(p,q)\\}$.
Therefore, we find a tree $T^{\prime\prime}$ in
$\mathscr{P}_{n}^{p,q}\setminus\\{D(p,q)\\}$ such that
$F(T^{\prime})<F(T^{\prime\prime})$, a contradiction to the choice of
$T^{\prime}$. Hence, $\iota(T^{\prime})=3.$

Let $T(x,y,z)$ be the graph obtained by identifying one leaf of $K_{1,x+1}$
(resp. $K_{1,z+1}$) with the center of $K_{1,y}$, which is depicted in Fig. 6.
As $T^{\prime}\in\mathscr{P}_{n}^{p,q}\setminus\\{D(p,q)\\}$ with
$\iota(T^{\prime})=3$, we have

$T^{\prime}\cong T(a,p-2,b),\ \ \ a\geq b\geq 1,a+b+1=q,$

or

$T^{\prime}\cong T(a^{\prime},q-2,b^{\prime}),\ \ \ \ a^{\prime}\geq
b^{\prime}\geq 1,a^{\prime}+b^{\prime}+1=p.$

Figure 6: Trees $T(x,y,z)$ and $T(a,0,b)(a\geq b\geq 1).$

######  Claim 1.

If $T^{\prime}\cong T(a,p-2,b)\ ($or $T^{\prime}\cong
T(a^{\prime},q-2,b^{\prime}))$, then $b=1$ $($or $b^{\prime}=1).$

Proof of Claim 1 We only show that if $T^{\prime}\cong T(a,p-2,b)$, we have
$b=1.$ Similarly, we can also show if $T^{\prime}\cong
T(a^{\prime},q-2,b^{\prime})$, then we have $b^{\prime}=1$. We omit the
procedure for the latter here.

Assume $b>1,$ let $u,v$ be two non-adjacent vertices of degree at least 2 in
$T(a,p-2,b)$ with $N_{T(a,p-2,q)}(v)=\\{w,w_{1},\ldots,w_{a}\\}$ and
$N_{T(a,p-2,b)}(u)=\\{w,z_{1},z_{2},\ldots,z_{b}\\}$. By Lemma 2.2, as
$f_{K_{1,a}}(v)\geq f_{K_{1,b}}(u)$, we have

$f_{T(a,p-2,b)}(v)\geq f_{T(a,p-2,b)}(u).$ (5.3)

Let $T^{*}=T(a,p-2,b)-\\{z_{2},z_{3},\ldots,z_{b}\\}$. Then we have

$f_{T^{*}}(v)>f_{T^{*}}(u),$ (5.4)

otherwise $f_{T^{*}}(v)\leq f_{T^{*}}(u)$. By Lemma 2.8, we have

$f_{T(a,p-2,b)}(v)<f_{T(a,p-2,b)}(u),$

which contradicts (5.3). Hence, the inequality in (5.4) holds.

On the other hand, $T(a+b-1,p-2,1)$ can be obtained by identifying the vertex
$v$ in $T^{*}$ with the center vertex of $K_{1,b-1}$; while $T(a,p-2,b)$ can
be obtained by identifying the vertex $u$ in $T^{*}$ with the center vertex of
$K_{1,b-1}$. By Corollary 2.4, we have

$F(T(a+b-1,p-2,1))>F(T(a,p-2,b)),$

which contradicts the choice of $T^{\prime}\,(=T(a,p-2,b)).$ Hence, $b=1$. ∎

If $p=2$, by Claim 1, we have $T^{\prime}\cong D(2,q),$ or $T^{\prime}\cong
B(2,q)$. Note that $T^{\prime}\in\mathscr{P}_{n}^{2,q}\setminus\\{D(2,q\\}$,
hence $T^{\prime}\cong B(2,q)$, as desired in this case.

If $p>2$, by Claim 1, we have $T^{\prime}\cong T(q-2,p-2,1)$ or
$T^{\prime}\cong T(p-2,q-2,1)=B(p,q)$. If $q=p,$ it is easy to see that
$T(q-2,p-2,1)\cong T(p-2,q-2,1)=B(p,q),$ our result follows immediately in
this subcase. Hence, it suffices to consider $q>p.$ In order to determine the
structure of $T^{\prime}$, it suffices to show that
$F(T(p-2,q-2,1))>F((q-2,p-2,1)).$

Note that $T(q-2,p-2,1)$ is obtained by identifying $u$ of $D(p-1,q-1)$ with a
leaf of $P_{3}$, and $T(q-2,p-2,1)$ is obtained by identifying $v$ of
$D(q-1,p-1)$ with a leaf of $P_{3}$, where $u$ is a vertex of degree $p-1$ in
$D(p-1,q-1)$, $v$ is a vertex of degree $q-1$ in $D(p-1,q-1)$. Notice that

$f_{D(p-1,q-1)}(u/v)=2^{p-2}<2^{q-2}=f_{D(p-1,q-1)}(v/u).$

So

$f_{D(p-1,q-1)}(u)<f_{D(p-1,q-1)}(v).$

Hence, by Corollary 2.4 we have $F((q-2,p-2,1))<F(T(p-2,q-2,1))$. Therefore,
for any $T\in\mathscr{P}_{n}^{p,q}\setminus\\{D(p,q)\\}$, $F(T)\leq
F(B(p,q)),q\geq p\geq 2$, with equality if and only if $T\cong B(p,q)$.

In order to complete the proof of Theorem 1.3 (ii), it suffices to show the
following claim.

######  Claim 2.

In the above situation, if $p\geq q\geq 2$ with $p+q=n$, then

$F(B(p,q))=\left\\{\begin{aligned} &3\cdot 2^{n-4}+3\cdot
2^{q-2}+2^{p-2}+n-1,&q\geq p>2,\\\ &2^{n-2}+n+2,&p=2.\end{aligned}\right.$

Proof of Claim 2 First consider $p=2$. Let $v$ be the vertex of degree $n-3$
in $B(2,n-2)$, hence $F(B(2,n-2))=f_{B(2,n-2)}(v)+F(B(2,n-2)-v).$

Note that

$f_{B(2,n-2)}(v)=4\cdot 2^{n-2-2}=2^{n-2}$

and

$F(B(2,n-2)-v)=F(P_{3}\cup(n-4)P_{1})={4\choose{2}}+n-4=n+2.$

Hence, by simple computation our result holds for $p=2$.

Now consider $p>2$. Let $v$ be the vertex of degree $q$ and $u$ the vertex of
degree $p-1$ in $B(p,q)$. Note that

$F(B(p,q))=f_{B(p,q)}(v*u)+f_{B(p,q)}(v/u)+f_{B(p,q)}(u/v)+F(B(p,q)-v-u).$

On the other hand,

$f_{B(p,q)}(v*u)=3\cdot 2^{p-2+q-2}=3\cdot 2^{n-4},\ \ \
f_{B(p,q)}(v/u)=3\cdot 2^{q-2},\ \ \ f_{B(p,q)}(u/v)=2^{p-2}$

and

$F(B(p,q)-v-u)=F((p-2+q-2)P_{1}\cup P_{2})=n-4+3=n-1.$

By simple calculation, our result also holds for $p>2.$ ∎

This completes the proof of Theorem 1.3 (ii).

(iii) If $p=1$, it is easy to see that
$\mathscr{T}_{n}^{k}=\\{P_{1}(\lfloor\frac{n-1}{2})\rfloor,\lceil\frac{n-1}{2}\rceil\\}$,
our result follows immediately. On the other hand, if $p=q$ or $p=q-1$, it is
easy to see that $P_{n}\in\mathscr{P}_{n}^{p,q}$, by Lemma 2.1, it is easy to
see that $P_{n}=P_{2p-1}(1,1)$ or $P_{n}=P_{2p-1}(0,1),$ minimizes the total
number of subtrees among $\mathscr{P}_{n}^{p,q}$. Hence, in what follows we
consider $1<p<\lfloor\frac{n}{2}\rfloor$. In order to complete the proof, it
suffices to show the following claim.

######  Claim 3.

If $T$ minimizes the total number of subtrees in $\mathscr{P}_{n}^{p,q},T\cong
P_{2p-1}(a,b)$, where $a\geq b\geq 1$ and $a+b=n-2p+1$.

Proof of Claim 3 If $1<p<\lfloor\frac{n}{2}\rfloor$, by (i) we know that
$T\not\cong D(p,q)$, so diam$(T)\geq 3$. If diam$(T)=3$, the claim follows
immediately. Hence in what follows we consider the trees whose diameter is
larger than 3. Suppose that $P_{r}=v_{1}\ldots v_{r}\,(r\geq 5)$ is one of the
longest path in $T$, we are to show that
$d_{T}(v_{3})=d_{T}(v_{4})=\cdots=d_{T}(v_{r-2})=2$ and $r=2p+1$. First assume
to the contrary that there exists $v\in\\{v_{3},v_{4},\ldots,v_{r-2}\\}$ such
that $d_{T}(v)\geq 3.$ Let

$i=\min\\{j:\ d_{T}(v_{j})\geq 3,\ \ \ 3\leq j\leq r-2\\},\ \ \ \
N_{T}(v_{i})=\\{v_{i-1},v_{i+1},z_{1},z_{2},\ldots,z_{s}\\},\ \ s\geq 1.$

Let $T_{0}$ be the component that contains $v_{i}$ in
$T-\\{z_{1},z_{2},\ldots,z_{s}\\}$. By Lemma 2.10, there exists $v_{t}\in
V_{P_{r}}$ such that

$f_{T_{0}}(v_{1})<\cdots<f_{T_{0}}(v_{t-1})<f_{T_{0}}(v_{t})\geq
f_{T_{0}}(v_{t+1})>\cdots>f_{T_{0}}(v_{r}).$

If $t<i,$ then we have $f_{T_{0}}(v_{i})>f_{T_{0}}(v_{r-1})>f_{T_{0}}(v_{r})$.
If $v_{i}$ and $v_{r-1}$ are in the same part, By Corollary 2.4, we have

$F(T)>F(T^{\prime}),$ (5.5)

where

$T^{\prime}=T-v_{i}z_{1}-\cdots-v_{i}z_{s}+v_{r-1}z_{1}+\cdots+v_{r-1}z_{s},\
\ \ \ T^{\prime}\in\mathscr{P}_{n}^{p,q}$

otherwise, $v_{i}$ and $v_{r}$ are in the same part, we have

$F(T)>F(T^{\prime\prime}),$ (5.6)

where

$T^{\prime\prime}=T-v_{i}z_{1}-\cdots-
v_{i}z_{s}+v_{r}z_{1}+\cdots+v_{r}z_{s},\ \ \ \
T^{\prime\prime}\in\mathscr{P}_{n}^{p,q}.$

If $t\geq i$, repeat as above, we have a
$T^{\prime\prime\prime}\in\mathscr{P}_{n}^{p,q}$ such that

$F(T)>F(T^{\prime\prime\prime}),\ \ \ \
T^{\prime\prime\prime}\in\mathscr{P}_{n}^{p,q}.$ (5.7)

Hence, (5.5)-(5.7) are contradictions to the choice of $T$. So we have $T\cong
P_{r}(a,b)$.

On the other hand, since $T\in\mathscr{P}_{n}^{p,q}$ with
$1<p<\lfloor\frac{n}{2}\rfloor$, it is easy to see that $r\leq 2p+1$. If
$r<2p+1$, it means that $v_{1}$ and $v_{r}$ are in different parts (otherwise
we have $p<\lceil\frac{r-2}{2}\rceil$ or $q<\lceil\frac{r-2}{2}\rceil$). As
$a\geq b$, we have $v_{1}\in V_{2}$ and $v_{r}\in V_{1}$, where $V_{1}$ and
$V_{2}$ are two parts of $V_{T}$ with $|V_{1}|=p,|V_{2}|=q$. Assume that
$N_{T}(v_{2})=\\{v_{3},v_{1},w_{2},\ldots,w_{a}\\},N_{T}(v_{r-1})=\\{v_{r-2},v_{r},u_{2},\ldots,u_{b}\\}$.
Let $\hat{T}=T-\\{v_{r},u_{2},\ldots,u_{b}\\}$. By Lemma 2.2, we have
$f_{\hat{T}}(v_{r-1})<f_{\hat{T}}(v_{1})$, by Corollary 2.4 we have

$F(T)>F(\tilde{T}),$ (5.8)

where

$\tilde{T}=T-v_{r-1}v_{r}-v_{r-1}u_{2}-\cdots-
v_{r}u_{b}+v_{1}v_{r}+v_{1}u_{2}+\cdots+v_{1}u_{b}.$

As $v_{r-1},v_{1}\in V_{2}$, $\tilde{T}\in\mathscr{P}_{n}^{p,q}$. Hence, (5.8)
is a contradiction to the choice of $T$. So we have $T\cong P_{2p-1}(a,b)$. ∎

By Claims 2 in the proof of Theorem 1.1(ii), together with Claim 3, $T\cong
P_{2p-1}(\lfloor\frac{n-2p+1}{2}\rfloor,\lceil\frac{n-2p+1}{2}\rceil)$, as
desired. ∎

######  Remark 1.

In view of Eq.(5.2), we have

$F(D(p,q))-F(D(p-1,q+1))=2^{p-2}-2^{q-1}<0$

for $q\geq p>1$. Hence, we have

$F(D(p,q))<F(D(p-1,q+1))<\cdots<F(D(1,n-1))=F(K_{1,n-1}),$ (5.9)

for $q\geq p>1$. Note that $D(p,q)$ maximizes the total number of subtrees
among $\mathscr{P}_{n}^{p,q}$, hence in view of (5.9) and Theorem 1.3(i), the
following corollary holds immediately.

######  Corollary 5.1 ([11]).

The star $K_{1,n-1}$ has $2^{n-1}+n-1$ subtrees, more than any other tree on
$n$ vertices.

##  6 Proof of Theorem 1.4

In this section we shall determine the sharp lower bound on the total number
of subtrees contained in a tree among $\mathscr{A}_{n}^{q}$.

Proof of Theorem 1.4 First we characterize the structure of the tree, say $T$,
minimizing the total number of subtrees in $\mathscr{A}_{n}^{q}.$ In order to
do so, it suffices to show that the diameter of $T$ is $n+1$. Without loss of
generality, we assume one of the longest paths in $T$ is
$P_{r+1}=v_{0}v_{1}\ldots v_{r}$. If $r=n+1$, our result holds obviously. So
in what follows, we assume that $r\leq n.$

For convenience, let

$N_{T}(v_{i})\setminus\\{v_{i-1},v_{i+1}\\}=\\{v_{i_{1}},v_{i_{2}},\ldots,v_{i_{q-2}}\\},\
\ \ \ \ \ i=1,2,\ldots,r-1.$

Hence,

$\bigcup_{i=1}^{r-1}N_{T}(v_{i})=\\{v_{1_{1}},v_{1_{2}},\ldots,v_{1_{q-2}},\ldots,v_{i_{1}},v_{i_{2}},\ldots,v_{i_{q-2}},v_{r_{1}},v_{r_{2}},\ldots,v_{r_{q-2}}\\}$
(6.1)

In fact, $(\bigcup_{i=1}^{r-1}N_{T}(v_{i}),\prec)$ is a total ordering set,
where $\prec$ is defined as following: for any
$v_{i_{j}},\,v_{t_{s}}\in\bigcup_{i=1}^{r-1}N_{T}(v_{i})$, we call
$v_{i_{j}}\prec v_{t_{s}}$ if $i<t$ or $i=t,j<s.$ Hence, we can order the
elements in (6.1) as following:

$v_{1_{1}}\prec v_{1_{2}}\prec\cdots\prec v_{1_{q-2}}\prec\cdots\prec
v_{i_{1}}\prec v_{i_{2}}\prec\cdots\prec v_{i_{q-2}}\prec v_{r_{1}}\prec
v_{r_{2}}\prec\cdots\prec v_{r_{q-2}}.$

Note that $r<n+1$, hence there must exists non-pendant vertex in
$\bigcup_{i=1}^{r-1}N_{T}(v_{i}).$ Choose the minimal element, say
$v_{l_{j}}$, under the order $\prec$ such that it is a non-pendant vertex.
Note that $P_{r+1}$ is the longest path in $T$, hence

$1<l<r-1.$ (6.2)

Thus, we can partition $T$ into two subtrees, say $S$ and $T_{0}$, such that
$E_{T}=E_{S}\cup E_{T_{0}},V_{T}=V_{S}\cup V_{T_{0}}$ and $V_{S}\cap
V_{T_{0}}=\\{v_{l_{j}}\\};$ see Fig. 7. For convenience, let
$N_{T_{0}}(v_{l_{j}})=\\{v_{0},w_{1},w_{2},\ldots,w_{q-1}\\}.$

Figure 7: An $q$-arc tree $T$.

Now we are in the position to apply Lemma 2.2 in the following setting:

$x\leftarrow v_{0},\ x_{i}\leftarrow v_{i},\
x_{\lfloor\frac{l}{2}\rfloor}\leftarrow v_{\lfloor\frac{l}{2}\rfloor}$

($z\leftarrow v_{\lceil\frac{l}{2}\rceil}$ if $l$ is odd)

$y\leftarrow v_{l_{j}},\ y_{i}\leftarrow v_{l+1-i},\
y_{\lfloor\frac{l}{2}\rfloor}\leftarrow v_{l+1-\lfloor\frac{l}{2}\rfloor}$

for $i=1,2,\ldots,\lfloor\frac{l}{2}\rfloor$.

Then

$\displaystyle X_{i}$ $\displaystyle=$ $\displaystyle K_{1,q-2},\ \ \ \
i=1,2,\ldots,\lfloor\frac{l}{2}\rfloor,$ $\displaystyle Y_{i}$
$\displaystyle=$ $\displaystyle K_{1,q-2},\ \ \ \
i=2,3,\ldots,\lfloor\frac{l}{2}\rfloor$

and $Y_{1}$ is the component in $T-v_{l-1}v_{l}-v_{l}v_{l_{j}}$ which contains
$v_{l}$. By direct calculation, it is easy to see that

$f_{X_{i}}(x_{i})=f_{Y_{i}}(y_{i})=2^{q-2},\ \ \ \
i=2,\ldots,\lfloor\frac{l}{2}\rfloor.$

On the other hand, in veiw of (6.2) we know that $Y_{1}\not\cong K_{1,q-2}$
and $f_{Y_{1}}(y_{1})>2^{q-2},$ while $f_{X_{1}}(x_{1})=2^{q-2}.$ Therefore,
we have

$f_{X_{1}}(x_{1})<f_{Y_{1}}(y_{1}).$

By Lemma 2.2, we have

$f_{S}(x)<f_{S}(y),$

where $S$ is defined as above. Therefore, by Corollary 2.4, we have

$F(T^{\prime})<F(T),$ (6.3)

where

$T^{\prime}=T-\\{v_{l_{j}}w_{1},v_{l_{j}}w_{2},\ldots,v_{l_{j}}w_{q-1}\\}+\\{v_{0}w_{1},v_{0}w_{2},\ldots,v_{0}w_{q-1}\\}.$

Inequality (6.3) is a contradiction to the choice of $T$. Hence, we obtain
$r=n+1$, i.e., $T\cong\hat{T}_{n}^{q},$ as desired.

In order to complete the proof of Theorem 1.4, it suffices to determine
$F(\hat{T}_{n}^{q})$. Choose one of the longest paths in $\hat{T}_{n}^{q}$ and
denote it by $P$. Let $v_{0}$ be one of its end-vertices. Then denote the
unique neighbour of $v_{0}$ by $v_{1}$; see Fig. 3. Hence, we have

$\displaystyle f_{\hat{T}_{n}^{q}}(v_{1})$ $\displaystyle=$ $\displaystyle
2^{q-1}\left(1+2^{q-2}+\cdots+2^{(n-2)(q-2)}+2^{(n-1)(q-2)}+2^{(n-1)(q-2)}\right),$
$\displaystyle f_{\hat{T}_{n-1}^{q}}(v_{1})$ $\displaystyle=$ $\displaystyle
1\left(1+2^{q-2}+\cdots+2^{(n-2)(q-2)}+2^{(n-1)(q-2)}+2^{(n-1)(q-2)}\right).$

Note that

$\displaystyle F(\hat{T}_{n}^{q})$ $\displaystyle=$ $\displaystyle
f_{\hat{T}_{n}^{q}}(v_{1})+F(\hat{T}_{n}^{q}-v_{1})$ $\displaystyle=$
$\displaystyle
f_{\hat{T}_{n}^{q}}(v_{1})+F((q-1)P_{1}\cup(\hat{T}_{n-1}^{q}-v_{1}))$
$\displaystyle=$ $\displaystyle
f_{\hat{T}_{n}^{q}}(v_{1})+F(\hat{T}_{n-1}^{q}-v_{1})+q-1$ $\displaystyle=$
$\displaystyle
f_{\hat{T}_{n}^{q}}(v_{1})+F(\hat{T}_{n-1}^{q})-f_{\hat{T}_{n-1}^{q}}(v_{1})+q-1.$

This gives

$\displaystyle F(\hat{T}_{n}^{q})-F(\hat{T}_{n-1}^{q})$ $\displaystyle=$
$\displaystyle f_{\hat{T}_{n}^{q}}(v_{1})-f_{\hat{T}_{n-1}^{q}}(v_{1})+q-1$
$\displaystyle=$ $\displaystyle
q-1+(2^{q-1}-1)\left(1+2^{q-2}+\cdots+2^{(n-2)(q-2)}+2^{(n-1)(q-2)}+2^{(n-1)(q-2)}\right)$
$\displaystyle=$ $\displaystyle
q-1+(2^{q-1}-1)\left(\frac{2^{n(q-2)}-1}{2^{q-2}-1}+2^{(n-1)(q-2)}\right)$
$\displaystyle=$ $\displaystyle
q-1-\frac{2^{q-1}-1}{2^{q-2}-1}+\frac{2^{(n-1)(q-2)}(2^{q-1}-1)^{2}}{2^{q-2}-1}.$

As $F(\hat{T}_{1}^{q})=F(K_{1,q})=2^{q}+q$, we have

$\displaystyle F(\hat{T}_{n}^{q})$ $\displaystyle=$ $\displaystyle
F(B_{1})+\sum_{i=2}^{n}\left[q-3-\frac{1}{2^{q-2}-1}+\frac{2^{(i-1)(q-2)}(2^{q-1}-1)^{2}}{2^{q-2}-1}\right]$
$\displaystyle=$
$\displaystyle(2^{q}+q)+(n-1)(q-3)-\frac{n-1}{2^{q-2}-1}+\frac{(2^{q-1}-1)^{2}}{2^{q-2}-1}\sum_{i=2}^{n}2^{(i-1)(q-2)}$
$\displaystyle=$
$\displaystyle\frac{2^{q-2}(2^{q-1}-1)^{2}(2^{(n-1)(q-2)}-1)}{(2^{q-2}-1)^{2}}-\frac{n-1}{2^{q-2}-1}+2^{q}+nq-3n+3.$

This completes the proof. ∎

######  Remark 2.

In particular, let $q=3$ in Theorem 1.4, we can obtain that just the $n$-leaf
binary caterpillar tree minimizes the total number of subtrees among $n$-leaf
binary trees, which is obtained by Székely and Wang in [11].

######  Corollary 6.1 ([11]).

For any $n\geq 2$, precisely the $n$-leaf binary caterpillar tree
$\hat{T}_{n-2}^{3},$ which has $2^{n+1}+2^{n-2}-n-4$ subtrees, minimizes the
number of subtrees among $n$-leaf binary trees.

##  7 Concluding remarks

In view of Theorem 1.3, we conjecture that one may show the counterparts of
these results for the Wiener index among the $n$-vertex trees with a given
$(p,q)$-bipartition. On the other hand, for the Wiener index, sharp upper and
lower bounds of trees with given degree sequence are determined; see [13, 17,
18]. It is natural for us to determine sharp upper and lower bounds on the
total number of subtrees of a tree with given degree sequence. It is difficult
but interesting and it is still open.

## References

  * [1] A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math. 66 (3) (2001) 211-249.
  * [2] I. Gutman, S.J. Cyvin, Kekulé, Structures in Benzenoid Hydrocarbons, Springer, Berlin, 1988.
  * [3] M. Fischermann, A. Hoffmann, D. Rautenbach, L.A. Székely, L. Volkmann, Wiener index versus maximum degree in trees, Discrete Appl. Math. 122 (1-3) (2002) 127-137.
  * [4] F. Jelen, E. Triesch, Superdominance order and distance of trees with bounded maximum degree, Discrete Appl. Math. 125 (2-3) (2003) 225-233.
  * [5] R. Kirk, H. Wang, Largest number of subtrees of trees with a given maximum degree, SIAM J. Discrete Math. 22 (2008) (3) 985-995.
  * [6] D. Rautenbach, A note on trees of maximum weight and restricted degrees, Discrete Math. 271 (2003) 335-342.
  * [7] C.W. Song, Counting special families of labelled trees, Ann. Comb. 10 (2) (2006) 271-283.
  * [8] L.A. Székely, H. Wang, Binary trees with the largest number of subtrees, Discrete Appl. Math. 155 (2007) (3) 374-385.
  * [9] L.A. Székely, H. Wang, On subtrees of trees, 2004 Industrial Mathematics Institute Research Reports 04:04, University of South Carolina, http://www.math.sc.edu/ imip/04.html, 2004.
  * [10] L.A. Székely, H.Wang, Binary trees with the largest number of subtrees with at least one leaf, 36th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, Congr. Numer. 177 (2005) 147-169.
  * [11] L.A. Székely, H. Wang, On subtrees of trees, Adv. Appl. Math. 34 (2005) (1) 138-155.
  * [12] A. Vince, H. Wang, The average order of a subtree of a tree, J. Combin. Theory Ser. B 100 (2010) (2) 161-170.
  * [13] H. Wang, The extremal values of the Wiener index of a tree with given degree sequence, Discrete Appl. Math. 156 (2008) (14) 2647-2654.
  * [14] H. Wang, Some results on trees, PhD Thesis, Department of Mathematics, University of South Carolina, 2005 (anticipated).
  * [15] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947) 17-20.
  * [16] W.G. Yan, Y.N. Ye, Enumeration of subtrees of trees, Theoret. Comput. Sci. 369 (2006) 256-268.
  * [17] X.D. Zhang, Y. Liu, M.X. Han, Maximum Wiener index of trees with given degree sequence, MATCH Commun. Math. Comput. Chem. 64 (3) (2010) 661-682.
  * [18] X.D. Zhang, Q.Y. Xiang, L.Q. Xu, R.Y. Pan, The Wiener index of trees with given degree sequences, MATCH Commun. Math. Comput. Chem. 60 (2) (2008) 623-644.


# RainAI - Precipitation Nowcasting from Satellite Data

Rafael Pablos Sarabia
Aarhus University
Department of Computer Science
Cordulus
<EMAIL_ADDRESS>
Joachim Nyborg
Cordulus
<EMAIL_ADDRESS>
Morten Birk
Cordulus
<EMAIL_ADDRESS>
Ira Assent
Aarhus University
Department of Computer Science
DIGIT Aarhus University Centre for
Digitalisation, Big Data and Data Analytics
<EMAIL_ADDRESS>

###### Abstract

This paper presents a solution to the Weather4Cast 2023 competition, where the
goal is to forecast high-resolution precipitation with an 8-hour lead time
using lower-resolution satellite radiance images. We propose a simple, yet
effective method for spatiotemporal feature learning using a 2D U-Net model,
that outperforms the official 3D U-Net baseline in both performance and
efficiency. We place emphasis on refining the dataset, through importance
sampling and dataset preparation, and show that such techniques have a
significant impact on performance. We further study an alternative cross-
entropy loss function that improves performance over the standard mean squared
error loss, while also enabling models to produce probabilistic outputs.
Additional techniques are explored regarding the generation of predictions at
different lead times, specifically through Conditioning Lead Time. Lastly, to
generate high-resolution forecasts, we evaluate standard and learned
upsampling methods. The code and trained parameters are available at
https://github.com/rafapablos/w4c23-rainai.

##  1 Introduction

Short-term rainfall prediction, also known as precipitation nowcasting, plays
a crucial role in various industries, such as agriculture, energy management,
emergency services, and transportation. The objective of precipitation
nowcasting is to generate accurate and high-resolution forecasts of rainfall
intensity within a specific geographic area over a short time span ranging
from 1 to 24 hours.

Traditional methods in this field rely on Numerical Weather Prediction (NWP)
and optical flow techniques, which are based on the physics of the atmosphere
and mathematical models [24, 4, 27]. However, the slow runtime of NWP models
make them unsuitable for short-term nowcasting, and optical flow methods are
constrained by their assumption of constant motion for precipitation features
over time [1, 28]. To address these limitations, there has been a shift
towards employing data-driven methods based on deep learning. These models
learn from historical observations and exploit the processing speed of modern
Graphics Processing Units (GPUs) to generate forecasts faster than NWPs and
capture more intricate patterns than optical-flow methods due to their non-
linear nature. However, the large spatial and temporal context required for
nowcasting presents a significant challenge for deep learning methods, which
must find a balance between efficient processing and capturing adequate
context across high spatial and temporal dimensions.

The Weather4Cast 2023 Competition on Super-Resolution Rain Movie Prediction
under Spatio-temporal Shifts at the 37th Conference on Neural Information
Processing Systems (NeurIPS 2023) provides an opportunity to work on the
intricate task of precipitation nowcasting. Similar to the Weather4Cast 2022
competition [15], this competition focuses on forecasting future high-
resolution rainfall events using lower resolution satellite radiances.
Successful rainfall prediction in this context requires data fusion, multi-
channel video frame prediction, and super-resolution techniques. Notably, a
new challenge in this year’s competition involves the quantitative prediction
of rainfall, contrasting with the previous year’s focus on determining whether
rain would surpass a predefined threshold.

Our work explores a simple architecture based on the 2D U-Net [29] as the
foundational structure and employs different encoders — specifically ResNet-18
[18] blocks or Swin Transformer [21], detailed in Sections 4.1.1 and 4.1.2
respectively. This is due to the ability of the 2D U-Net to effectively
process spatial dimensions in the input data. The alternative encoders are
meant to enhance the original 2D U-Net to capture more complex and long-term
dependencies. Emphasis is placed on optimizing the dataset by applying
sampling and problem-specific modifications as outlined in Section 4.2. To
enhance training, we adopt a classification approach with the cross-entropy
loss function, elaborated on in Section 4.3. Another proposal consists of
extending the model to condition the output to the required lead time instead
of generating all timesteps simultaneously (Section 4.4). Additionally, we
incorporate super-resolution techniques to derive high-resolution predictions
from the central region of the model’s output, explained in Section 4.5.

The models we propose surpass the official baseline across the core,
nowcasting, and transfer-learning leaderboards, as measured by the average
Critical Success Index (CSI) at various intensity thresholds. In comparison to
other submissions, our best models rank within the top 5 teams on each
leaderboard.

##  2 Related Work

We classify existing efforts in nowcasting into two paradigms: traditional and
deep learning-based. The fundamental distinction between traditional and deep
learning methods is that the former rely on physical models while the latter
models learn from historical weather data including radar maps, satellite
images, and recorded meteorological variables such as previous precipitation
or wind.

The traditional approaches include Numerical Weather Prediction (NWP) models
and optical flow models such as RainyMotion [4] and PySteps [27]. NWP models
have been established to predict the weather based on mathematical models
[24], but they are dependent on initial and boundary conditions at the top,
lateral, and lower boundaries of the model domain. In order to obtain
probabilistic and better forecasts, ensemble NWP systems are used to simulate
coupled physical equations of the atmosphere with different perturbations and
initial conditions [33]. With respect to optical-flow methods, they assume
that the movement of radar echoes along a fixed motion field can capture the
evolution of precipitation for a few hours without any changes in intensity.
Therefore, they estimate the motion field and extrapolate radar echoes to
create a forecast. These forecasts can also be combined with ensembles to
generate more accurate probabilistic forecasts. These traditional approaches
for precipitation nowcasting based on physical models require high computing
power, especially for ensemble models, so the spatial and temporal resolution
tends to be limited. Additionally, due to their convergence time, they are not
the most adequate for precipitation nowcasting, where the primary interest is
in the first few hours of the forecast. With respect to extrapolation-based
approaches, they tend to overestimate precipitation and not cover the region
with rain properly [28].

Due to the effectiveness of deep learning in a wide range of tasks,
particularly in computer vision and natural language processing, there has
been a growing interest in applying deep learning to precipitation nowcasting.
Deep learning models have demonstrated improved forecast quality, as measured
by per-grid-cell metrics, due to their direct optimization and fewer inductive
biases. Deep learning methods leverage modern Graphical Processing Units (GPU)
to generate forecasts in seconds [9] and can capture complex non-linear
precipitation phenomena due to their ability to identify patterns in high-
dimensional data [12].

A number of deep learning approaches for precipitation nowcasting are based on
the U-Net architecture [29] consisting of an encoder-decoder architecture with
Convolutional Neural Network (CNN) layers. While this architecture has no
explicit modeling of memory and simply manages the temporal dimension as an
additional channel, multiple precipitation nowcasting models based on the
original U-Net architecture have been successfully employed [1, 34, 5, 10].
Additional architectures, including a variety of recurrent neural networks
(RNNs), have been proposed with a dedicated mechanism to handle temporal
information and fully capture temporal dynamics and dependencies [30, 31, 23].
The main challenge with RNNs is training time due to its recurrent connections
and unrolling of the time sequences.

Additional advanced deep learning techniques used in weather forecasting
include MetNet [32], MetNet2 [9] and MetNet3 [3] to forecast precipitation in
the United States for up to 8, 12, and 24 hours respectively. While the
resources required for these models are extremely large, many of the insights
and decisions can be transferred to smaller models with less parameters and
inputs with lower dimensionality. Some of these insights cover data
preprocessing and transformations, problem formulation, architecture choices,
training optimization, and evaluation metrics. [7, 28, 6, 37, 26] also make
use of large models with complex architectures and training including Vision
Transformers [8], Swin Transformers [21], MaxVit [35], PhyDNet [17],
Earthformer [11], and Generative Adversarial Training [13]. A main weakness of
most of these models is their complexity and required computing power when
compared to more simple architectures such as the 2D U-Net.

##  3 Weather4Cast Challenge & Dataset

The task for the competition involves predicting 32 ground-radar images that
quantitatively represent the amount of rainfall for the next 8 hours, given an
input sequence of satellite observations for the preceding hour (4 time
slots). The organizers provide satellite and radar images for 7 regions in
Europe with different precipitation characteristics, spanning from February
2019 to December 2020. Additionally, for evaluating spatial and temporal
transfer learning, 3 more regions and data for 2021 are provided. For
precipitation nowcasting, radar data is more useful and has higher accuracy
and resolution than satellite data. However, satellite data is used as input
to the models in this competition because radar observations are expensive to
obtain and not available in many parts of the world.

The input satellite data is obtained by geostationary satellites operated by
the European Organisation for the Exploitation of Meteorological Satellites
(EUMETSAT) with a spatial resolution of about 12 x 12 km2 and a temporal
resolution of 15 minutes. This data contains 11 channels, including visible
and near-infrared (VIS), thermal infrared (IR), and water vapor absorption
(WV) bands for the selected regions. Given the input patch has size 252 x 252
pixels, the input data covers an area of about 3,024 x 3,024 km2 for each
region.

For each input region of about 3,024 x 3,024 km2, the objective is to forecast
precipitation in the central area of the region. In order to evaluate rainfall
predictions in each region, rainfall rates, derived from ground-radar
reflectivity, are provided by the Operational Program for Exchange of Weather
Radar Information (OPERA) radar network. This radar data is provided in
15-minute intervals in patches of size 252 x 252 pixels with a spatial
resolution of about 2 x 2 km2, covering the central area of about 504x504 km2
for each region.

The challenge involves predicting precipitation rates in a region of size 504
x 504 km2, corresponding to the central region of a much larger area covering
about 3,024 x 3,024 km2 for which satellite measurements are available. This
implies about 1,260 km of spatial context in each direction. Considering the
required 64-85 km of context per hour of lead time in each spatial dimension
[9], enough spatial context is provided to generate predictions for up to
15-19 hours.

Regarding the available data for the 7 regions and 2 years used for training,
there are 228,928 training sequences generated by the provided code with a
sliding window, and 840 predefined sequences for validation. While this is a
large amount of training data, the data is highly unbalanced towards no rain,
which makes it difficult to train an unbiased model. Table 1 shows the data
distribution of the validation data for different rainfall intensities using
one of the proposed classification scales from PySTEPS [27]. Note that not
only do lower rainfall intensities have many more events, but they also cover
smaller ranges.

Table 1: Rainfall distribution over the validation dataset (7 regions,
2019-2020)

Intensity (mm/h) | Observations (%)
---|---
< 0.08 | 88.05
(0.08, 0.16] | 3.57
(0.16, 0.25] | 1.71
(0.25, 0.40] | 1.60
(0.40, 0.63] | 1.53
(0.63, 1.0] | 1.34
(1.0, 1.6] | 1.00
(1.6, 2.5] | 0.61

Intensity (mm/h) | Observations (%)
---|---
(2.5, 4.0] | 0.35
(4.0, 6.3] | 0.15
(6.3, 10.0] | 0.06
(10.0, 16.0] | 0.02
(16.0, 25.0] | 0.01
(25.0, 40.0] | 0.00
> 40.0 | 0.00

In addition, for each of the regions, static data with latitude, longitude,
and topological height is provided.

##  4 Model Architecture & Optimizations

The contributions for the competition, detailed in this section, focus on
different architectures, optimization of the dataset, and changes to the
problem formulation. These changes include approaching the problem as
classification with cross-entropy loss, integration of lead time conditioning,
and the incorporation of super-resolution techniques to obtain the final high-
resolution precipitation forecasts.

###  4.1 2D U-Net

Given its success in various tasks, including precipitation nowcasting [1, 5,
10, 34], the original 2D U-Net architecture [29] is studied. For this
challenge, modifications are made to the original U-Net by incorporating
Residual Networks (ResNet) [18] blocks or Swin Transformer [21] as the
encoder.

The U-Net is a fully-convolutional architecture consisting of an encoder to
generate feature maps containing high-level information and a decoder to
obtain full-resolution outputs. The use of skip connections is essential to
combine the high-level information obtained with the encoder with the detailed
spatial information before downsampling. While retaining the original concepts
from the U-Net architecture, various U-Net architectures have been proposed to
enhance its performance and adapt it to different tasks [25, 2, 16].

We propose the simple 2D U-Net instead of the more computational complex 3D
U-Net baseline provided. In the 2D U-Net, which inherently lacks the ability
to directly manage time, time is processed by extending the number of channels
for the filters in the input and output layers of the U-Net to include the
temporal dimension. This means that time is stacked on top of channels, so for
an input with dimensions T x C x H x W, the input to the 2D U-Net architecture
becomes T*C x H x W. Similarly, the output of the 2D U-Net of size T’*C’ x H x
W is unstacked to T’ x C’ x H x W, where T’ is the forecasted timesteps and C’
the output channels for each timestep. Whereas the 3D U-Net preserves the
temporal dimension throughout the model, the 2D U-Net only combines
information across time at the input layer, yet still manages to improve
performance.

####  4.1.1 ResNet 2D U-Net

One alternative to the original 2D U-Net consists of using ResNet blocks as
the encoder to address the vanishing gradient problem in deep neural networks.
ResNet employs residual connections or "identity shortcut" connections to skip
one or more layers, providing an alternative shortcut path for gradient flow
from later layers to earlier layers [18].

By replacing the U-Net encoder with a ResNet-18 encoder, the architecture is
able to learn more complex features while still training efficiently with the
aid of residual connections. Note that skip connections and residual
connections are similar, but U-Net uses skip connections to make upsampling
better, while ResNet uses residual connections for gradient flow. In the
proposed architecture, every encoder block has a corresponding decoder block
that processes the concatenation of the feature map coming from the encoder
via skip connection and the upsampled feature map from the previous block in
the decoder.

####  4.1.2 Swin 2D U-Net

We also study the applications of Transformers, specifically Swin Transformer
[21], as the encoder. This choice is motivated by the Swin Transformer’s
capability to compute attention, facilitating the modeling of long-range
dependencies to generate accurate forecasts. Notably, the Swin Transformer
enhances the original Vision Transformer [8] by introducing Shifted Windows,
enabling global attention with local computations in non-overlapping windows.

The Swin Transformer constructs a hierarchical representation by starting with
small-sized patches and progressively merging neighboring patches in deeper
Transformer layers. It computes multi-head self-attention [36] locally within
non-overlapping windows that partition an image with a fixed number of patches
per window. The Swin Transformer also introduces relative position bias in the
attention computation for each head based on the spatial positions of each
token.

The hierarchical representation obtained with the Swin Transformer is used by
the decoder and skip connections to upsample the encoded feature maps and
generate the required output.

###  4.2 Dataset Optimization

We further improve model performance and training time by maximizing the
impact of training data. We use sampling techniques and adapt input data by
selecting the appropriate input features and context for the problem.

####  4.2.1 Data Sampling

Sampling is essential as the dataset is large and ground-radar observations
mostly contain regions with little or no precipitation that heavily bias the
model towards predicting no rain. Importance sampling [19] is used to create a
balanced dataset more representative of high precipitation by reducing the
number of samples containing no precipitation. This optimization allows the
model to train faster and improve performance with observations that
positively help the model to learn from rainfall events.

Importance sampling computes $q_{n}$ for every sample as the acceptance
probability for a given sample to be included into the subset of samples. This
is calculated as $q_{n}=min{(1,q_{min}+x_{n}^{sat})}$, with $x_{n}^{sat}$
being the average of the saturated values over the output region
$\frac{1}{C}\sum_{c}x_{n,c}^{sat}$. Note that $x_{n,c}^{sat}$ is computed as
$1-exp(-x_{n,c})$ for every time step and pixel on the patch region.
$q_{min}$, the minimum probability of inclusion even if there is not any
rainfall, is set to $1x10^{-6}$ to obtain more events with high precipitation
[28]. The motivation for these formulas is to guarantee a minimum probability
of inclusion for patches without significant precipitation, while still
favouring patches with significant rain.

####  4.2.2 Data Preparation

In addition to the sampling process, we tailor the dataset to address the
presented precipitation nowcasting problem with its requirements and available
data. Consequently, the provided code is modified to load static data along
with each sample, incorporating latitude, longitude, and topological height
for each position within the input patch. This additional information holds
the potential to impact the models by introducing relevant data that
influences weather conditions, as discussed in previous studies [7, 3].

However, it is not only important during data preparation for precipitation
nowcasting to consider the features to be included in the input, but also the
context provided. While larger context can enrich the information available
for the models to learn from, it may pose challenges due to the increased
dimensionality of the data, significantly affecting computation requirements
and training time. For this specific problem, in terms of temporal context,
only four timesteps representing the previous hour are provided and remain
unmodified. However, as detailed in Section 3, the spatial context provided is
sufficient for generating forecasts with a lead time of up to 15-19 hours.
Given that the competition focuses on forecasts up to 8 hours ahead, the
spatial context of the input is reduced to optimize for training time and
facilitate learning without introducing unnecessary data. As a result, the
input patches are cropped from the original 252 x 252 pixels to 128 x 128
pixels, providing a spatial context of 516 km in each direction, which we find
sufficient for the 8-hour prediction.

###  4.3 Cross Entropy Loss

While the initially provided loss function is Mean Squared Error (MSE), a
regression loss, classification losses such as cross-entropy have been used
for precipitation nowcasting to obtain better performance [32, 9, 3] and
generate probabilistic forecasts that provide more information. For example, a
summer shower, predicted with a 100% probability, may produce 2mm of rain,
while a thunderstorm generating 10mm of rain might only have a 20%
probability. Despite both events resulting in the same 2mm of rain per hour,
the appropriate actions taken in response to each would differ significantly.
Thus, probabilistic forecasts are more meaningful than intensity predictions.

Approaching precipitation nowcasting as a classification problem requires the
use of predefined classes or buckets to categorize different levels of rain
intensities. The classes utilized align with those presented in Table 1,
aiming to establish narrower ranges for lower precipitation values where
observations are more abundant, while still being capable of representing
instances of heavy precipitation.

Another advantage of targeting precipitation nowcasting as a classification
problem is that weights can be assigned to the different classes to deal with
unbalanced datasets. The weights are set to be inversely proportional to
frequency of classes, so that less frequent classes (those with high
precipitation events) get higher weight than those that appear often (no rain
or low rain).

While probabilistic outputs are more informative, forecast intensities may be
required for some use cases, such as submitting to the leaderboard or
evaluating against some metrics. In the case of cross-entropy, where
probabilities are allocated across different classes that sum up to 1, the
average of each bucket is multiplied by its probability, and the resulting
values are summed to yield the final precipitation value. However, it should
be noted that the probability distribution itself provides more informative
insights than solely the computed value.

###  4.4 Conditioning Lead Time

Precipitation nowcasting models can be designed to output predictions for all
time steps in a single iteration or one at a time. While the initial approach
produces all precipitation forecasts for the required lead times at once, the
concept of conditioning lead time introduced in the MetNet [32] architecture
is studied.

With conditioning lead time, a forward pass of the model makes a prediction
for a single lead time. The required single lead time is provided as input to
the model to condition every aspect of the computation. While in MetNet lead
time is provided as a one-hot encoding, we provide it as a single value.
Therefore, when using conditioning lead time, the model includes an additional
channel as input that is entirely filled with the required timestep.

It is essential to note that this approach differs from autoregressive
methods, where the model consistently predicts the next timestep using
previously predicted timesteps as input. In our scenario, the model does not
utilize any predictions as inputs and can generate a forecast for the desired
lead time independently and simultaneously. Designing models able to forecast
multiple timesteps yields improved results because autoregressive approaches
incorporate both past observations and predicted forecasts, causing errors in
the intermediate forecasts to accumulate and impact future predictions that
rely on them as input.

###  4.5 Crop & Upsample

The output of the 2D U-Net architecture has the same spatial dimensions as its
input. This means that for an input sequence of size 128 x 128 pixels, a
forward pass through the U-Net will generate an output of size 128 x 128
pixels. However, the labels correspond to the central patch of size 42 x 42
pixels. Therefore, to guide the precipitation nowcasting model, we take the
central 42 x 42 pixels patch and upsample to the 252 x 252 pixels label. This
cropping and upsample was introduced in MetNet [9] and is due to the different
spatial resolutions of the input and labels, as explained in Section 3.

An alternative would be to let the output of the U-Net be the forecast for the
label region without cropping and upsampling the data. However, this would
require the U-Net to learn how to obtain a high resolution output of the
central region of the input region, which is significantly more challenging.

For upsampling, different methods are studied, including standard upsample
algorithms such as nearest neighbor and bilinear interpolation, but also more
complex super-resolution architectures such as Enhanced Deep Super Resolution
(EDSR) [20] and NinaSR [14]. Nearest neighbor upsample copies the value from
the nearest pixel, and bilinear uses all nearby pixels to calculate the
pixel’s value using linear interpolations. Both super-resolution
architectures, EDSR and NinaSR, use residual blocks to improve over simple CNN
techniques by making connections between the early layers of the network and
the late ones, achieving good performance in terms of evaluation metrics and
training time.

##  5 Experimental Evaluation

All models have been trained on Amazon AWS, utilizing a single Amazon EC2 G5
instance equipped with an NVIDIA A10G Tensor Core GPU. Table 2 summarizes the
experiments conducted for the respective leaderboards, showcasing the achieved
score, training time, and a brief description. Additional information on the
configuration of the experiments can be found in Table 3 in the Appendix.

Table 2: Experiments with obtained scored on the respective leaderboard. Leaderboard | Experiment | Score | Time (h) | Comments
---|---|---|---|---
Core | Official Baseline | 0.0444 | - | Official Baseline based on 3D U-Net
Core | exp1 | 0.0306 | 11.5 | ResNet 2D U-Net & Cross-Entropy
Core | exp2 | 0.0491 | 1.7 | exp1 & sampling
Core | exp3 | 0.0345 | 1.7 | exp2 & buckets for CSI thresholds
Core | exp4 | 0.0502 | 1.5 | exp2 & crop and bilinear upsample
Core | exp5 | 0.0477 | 2.5 | exp4 & Conditioning Lead Time
Core | exp6 | 0.0451 | 1.1 | exp4 & class weights
Core | exp7 | 0.0482 | 2.5 | exp4 & EDSR upsample
Core | exp8 | 0.0507 | 3.2 | exp4 & NinaSR upsample
Nowcasting | Official Baseline | 0.0482 | - | Official Baseline based on 3D U-Net
Nowcasting | exp1 | 0.0585 | 3.2 | exp8 from Core (16 first predictions)
Nowcasting | exp2 | 0.0580 | 0.8 | U-Net for 4h
Nowcasting | exp3 | 0.0552 | 2.0 | Swin for 4h
Transfer | Official Baseline | 0.0459 | - | Official Baseline based on 3D U-Net
Transfer | exp1 | 0.0566 | 3.2 | exp8 from core (16 first predictions)
Transfer | exp2 | 0.0584 | 0.8 | exp2 from Nowcasting
Transfer | exp3 | 0.0531 | 2.0 | exp3 from Nowcasting

The best results for the core challenge are achieved with experiment #8, which
uses the ResNet-18 2D U-Net architecture, the optimized dataset, cross-entropy
loss function, and cropping and upsampling with NinaSR. This particular model
is also utilized for the 4-hour prediction in both the nowcasting and transfer
learning leaderboards (exp1), focusing solely on the initial 16 predicted
timesteps. Remarkably, this model excels in the nowcasting leaderboard,
outperforming other models trained exclusively for a 4-hour prediction.
However, in the transfer learning leaderboard, this is not the case and
training a new model for the 4-hour prediction appears to yield superior
results indicating that for the transfer learning task, the model does not
benefit from observing longer lead times.

As anticipated, the visualization of the Critical Success Index (CSI) across
the various thresholds of the leaderboard at the required lead times, as
depicted in Figure 1, reveals a decrease in values for longer lead times due
to increased uncertainty and complexity. Nevertheless, it is essential to note
that throughout the experiments, the CSI values for thresholds above 5mm/h
consistently score 0, indicating a general inability to predict these high-
precipitation events, likely due to the under-represented examples with more
than 5mm/h as shown in Table 1.

Figure 1: Evolution of Critical Success Index (CSI) at different thresholds
for the required lead times for the core challenge (exp4).

In Figure 2, ground truth and predictions for a validation sequence using the
model from experiment #4 are presented. This experiment is the same as
experiment #8 just explained, with the only change being that upsampling is
performed via bilinear interpolation, so it was faster to train with minimal
decrease in evaluation metrics. Please note that the precipitation in the
bottom left corner is detected, but the resolution and intensity are not as
high as in the ground truth. This is one of the problems that has been
identified, most likely due to the lack of high-resolution input data.

Figure 2: Visualization of ground truth (top) and predicted precipitation
(bottom) for the required lead times for the core challenge for a validation
sequence of the provided dataset (exp4).

##  6 Conclusion & Future Work

The presented work is a part of the Weather4Cast 2023 NeurIPS competition,
focusing on precipitation nowcasting using low-resolution input satellite
observations. This challenge requires the application of data fusion, multi-
channel video frame prediction, and super-resolution techniques.

The proposed models leverage the 2D U-Net architecture, incorporating either
ResNet-18 or Swin Transformer blocks, an optimized dataset, cross-entropy loss
function, conditioning lead time, and upsampling methods. The best performing
models use the ResNet-18 2D U-Net architecture, the optimized dataset, cross
entropy loss, and NinaSR upsample. However, similar performance is achieved
with bilinear interpolation and it is faster to train. While not all these
optimizations are necessarily employed by the best-performing models,
specifically the Swin Transformers as the encoder or conditioning lead time,
experiments that incorporate these enhancements consistently outperform the
official baseline on the leaderboard in terms of evaluation metrics.

Moreover, this challenge highlights the complexity of successfully performing
precipitation nowcasting from low-resolution satellite observations,
particularly to anticipate high-precipitation events.

A primary area of concern that we will aim to address in future work is
enhancing the accuracy when forecasting high-precipitation events. We believe
that adding specific modules with different loss functions to the architecture
could assist in identifying and predicting these instances of high
precipitation. These new modules can guide the architecture to learn in an
easier way, similar to the Crop & Upsample optimization. Regarding loss
functions, a limitation of cross-entropy is that it assigns the same loss for
incorrect predictions regardless of the difference between the prediction and
the ground truth.

In order to improve the overall performance, MetNet-2 [9] and MetNet-3 [3]
propose optimizing the conditioning lead time strategy. Instead of merely
having the required timestep as input to the model, this optimization entails
influencing computation at every layer based on the lead time with a bias and
scale vector derived from the required timestep.

Finally, another focus area is processing the temporal dimension of the input
sequences to learn more intricate precipitation patterns and enhance overall
performance by utilizing memory-based architectures or architectures that
independently process the temporal dimension (i.e., Video Swin Transformer
[22]).

## Appendix

Table 3 provides a breakdown of the experiments conducted for each leaderboard
in the Weather4Cast 2023 competition. In the table, RU and SU refer to ResNet
2D U-Net and Swin 2D U-Net models, respectively. CLT, LR, and BS correspond to
conditioning lead time, learning rate, and batch size, with batch size
indicating both the size that fits in memory and the effective batch size for
gradient updates. Lead Time, LT, represents the maximum number of timesteps
for which the model is designed to make predictions. Cross-entropy loss
function is utilized for the training of all models, and static data is
incorporated in every experiment except for experiment #1.

Table 3: Details for the experiments run to train the different models. Experiment | Model | Samples | Ep | Buckets | Up | CLT | LR | BS | LT
---|---|---|---|---|---|---|---|---|---
Core exp1 | RU | 220K | 1 | mmh | No | No | 1E-4 | 16 (16) | 32
Core exp2 | RU | 15K | 4 | mmh | No | No | 1E-4 | 16 (16) | 32
Core exp3 | RU | 15K | 4 | w4c23_1 | No | No | 1E-4 | 16 (16) | 32
Core exp4 | RU | 15K | 4 | mmh | Bilinear | No | 1E-4 | 8 (16) | 32
Core exp5 | RU | 15K | 3 | mmh | Bilinear | Yes | 1E-4 | 2 (32) | 32
Core exp6 | RU | 10K | 4 | mmh_w | Bilinear | No | 1E-3 | 16 (16) | 32
Core exp7 | RU | 15K | 4 | mmh | EDSR | No | 1E-4 | 8 (16) | 32
Core exp8 | RU | 15K | 4 | mmh | NinaSR | No | 1E-4 | 8 (16) | 32
Nowcast exp1 | RU | 15K | 4 | mmh | NinaSR | No | 1E-4 | 8 (16) | 32
Nowcast exp2 | RU | 10K | 13 | mmh | Nearest | No | 1E-4 | 4 (32) | 16
Nowcast exp3 | SU | 2K | 19 | w4c23_2 | Nearest | Yes | 1E-4 | 2 (128) | 16
Transfer exp1 | RU | 15K | 4 | mmh | NinaSR | No | 1E-4 | 8 (16) | 32
Transfer exp2 | RU | 10K | 13 | mmh | Nearest | No | 1E-4 | 4 (32) | 16
Transfer exp3 | SU | 2K | 19 | w4c23_2 | Nearest | Yes | 1E-4 | 2 (128) | 16

## References

  * [1] Shreya Agrawal et al.  “Machine Learning for Precipitation Nowcasting from Radar Images” arXiv:1912.12132 [cs, stat]  arXiv, 2019  URL: http://arxiv.org/abs/1912.12132
  * [2] Md. Alom et al.  “Recurrent Residual Convolutional Neural Network based on U-Net (R2U-Net) for Medical Image Segmentation”  In _CoRR_ abs/1802.06955, 2018  arXiv: http://arxiv.org/abs/1802.06955
  * [3] Marcin Andrychowicz et al.  “Deep Learning for Day Forecasts from Sparse Observations” arXiv:2306.06079 [physics]  arXiv, 2023  URL: http://arxiv.org/abs/2306.06079
  * [4] Georgy Ayzel, Maik Heistermann and Tanja Winterrath  “Optical flow models as an open benchmark for radar-based precipitation nowcasting (rainymotion v0.1)”  In _Geoscientific Model Development_ 12.4, 2019, pp. 1387–1402  DOI: 10.5194/gmd-12-1387-2019
  * [5] Georgy Ayzel, Tobias Scheffer and Maik Heistermann  “RainNet v1.0: a convolutional neural network for radar-based precipitation nowcasting”  In _Geoscientific Model Development_ 13.6, 2020, pp. 2631–2644  DOI: 10.5194/gmd-13-2631-2020
  * [6] Kaifeng Bi et al.  “Accurate medium-range global weather forecasting with 3D neural networks”  In _Nature_ 619.7970, 2023, pp. 533–538  DOI: 10.1038/s41586-023-06185-3
  * [7] Kaifeng Bi et al.  “Pangu-Weather: A 3D High-Resolution Model for Fast and Accurate Global Weather Forecast” arXiv:2211.02556 [physics]  arXiv, 2022  URL: http://arxiv.org/abs/2211.02556
  * [8] Alexey Dosovitskiy et al.  “An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale” arXiv:2010.11929 [cs]  arXiv, 2021  URL: http://arxiv.org/abs/2010.11929
  * [9] Lasse Espeholt et al.  “Skillful Twelve Hour Precipitation Forecasts using Large Context Neural Networks” arXiv:2111.07470 [physics]  arXiv, 2021  URL: http://arxiv.org/abs/2111.07470
  * [10] Jesús García Fernández and Siamak Mehrkanoon  “Broad-UNet: Multi-scale feature learning for nowcasting tasks”  In _Neural Networks_ 144, 2021, pp. 419–427  DOI: 10.1016/j.neunet.2021.08.036
  * [11] Zhihan Gao et al.  “Earthformer: Exploring Space-Time Transformers for Earth System Forecasting” Publisher: arXiv Version Number: 2, 2022  DOI: 10.48550/ARXIV.2207.05833
  * [12] Ian Goodfellow, Yoshua Bengio and Aaron Courville  “Deep Learning”  MIT Press, 2016
  * [13] Ian Goodfellow et al.  “Generative Adversarial Nets”  In _Advances in Neural Information Processing Systems_ 27 Curran Associates, Inc., 2014  URL: https://proceedings.neurips.cc/paper_files/paper/2014/file/5ca3e9b122f61f8f06494c97b1afccf3-Paper.pdf
  * [14] Gabriel Gouvine  “NinaSR: Efficient Small and Large ConvNets for Super-Resolution” Publication Title: GitHub repository  GitHub, 2021  DOI: 10.5281/zenodo.4868308
  * [15] Aleksandra Gruca et al.  “Weather4cast at NeurIPS 2022: Super-Resolution Rain Movie Prediction under Spatio-temporal Shifts”, 2022
  * [16] Steven Guan, Amir A. Khan, Siddhartha Sikdar and Parag V. Chitnis  “Fully Dense UNet for 2D Sparse Photoacoustic Tomography Artifact Removal”  In _CoRR_ abs/1808.10848, 2018  arXiv: http://arxiv.org/abs/1808.10848
  * [17] Vincent Le Guen and Nicolas Thome  “Disentangling Physical Dynamics from Unknown Factors for Unsupervised Video Prediction” arXiv:2003.01460 [cs]  arXiv, 2020  URL: http://arxiv.org/abs/2003.01460
  * [18] Kaiming He, Xiangyu Zhang, Shaoqing Ren and Jian Sun  “Deep Residual Learning for Image Recognition” arXiv:1512.03385 [cs]  arXiv, 2015  URL: http://arxiv.org/abs/1512.03385
  * [19] Herman Kahn  “Use of Different Monte Carlo Sampling Techniques”  Santa Monica, CA: RAND Corporation, 1955
  * [20] Bee Lim et al.  “Enhanced Deep Residual Networks for Single Image Super-Resolution” arXiv:1707.02921 [cs]  arXiv, 2017  URL: http://arxiv.org/abs/1707.02921
  * [21] Ze Liu et al.  “Swin Transformer: Hierarchical Vision Transformer using Shifted Windows” arXiv:2103.14030 [cs]  arXiv, 2021  URL: http://arxiv.org/abs/2103.14030
  * [22] Ze Liu et al.  “Video Swin Transformer” arXiv:2106.13230 [cs]  arXiv, 2021  URL: http://arxiv.org/abs/2106.13230
  * [23] Chuyao Luo, Xutao Li and Yunming Ye  “PFST-LSTM: A SpatioTemporal LSTM Model With Pseudoflow Prediction for Precipitation Nowcasting”  In _IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing_ 14, 2021, pp. 843–857  DOI: 10.1109/JSTARS.2020.3040648
  * [24] K Mylne et al.  “Guidelines for Ensemble Prediction System”  World Meteorological Organization, 2022
  * [25] Ozan Oktay et al.  “Attention U-Net: Learning Where to Look for the Pancreas”  In _CoRR_ abs/1804.03999, 2018  arXiv: http://arxiv.org/abs/1804.03999
  * [26] Jiří Pihrt, Rudolf Raevskiy, Petr Šimánek and Matej Choma  “WeatherFusionNet: Predicting Precipitation from Satellite Data” arXiv:2211.16824 [cs]  arXiv, 2022  URL: http://arxiv.org/abs/2211.16824
  * [27] Seppo Pulkkinen et al.  “Pysteps: an open-source Python library for probabilistic precipitation nowcasting (v1.0)”  In _Geoscientific Model Development_ 12.10, 2019, pp. 4185–4219  DOI: 10.5194/gmd-12-4185-2019
  * [28] Suman Ravuri et al.  “Skilful precipitation nowcasting using deep generative models of radar”  In _Nature_ 597.7878, 2021, pp. 672–677  DOI: 10.1038/s41586-021-03854-z
  * [29] Olaf Ronneberger, Philipp Fischer and Thomas Brox  “U-Net: Convolutional Networks for Biomedical Image Segmentation” Publisher: arXiv Version Number: 1, 2015  DOI: 10.48550/ARXIV.1505.04597
  * [30] Xingjian Shi et al.  “Convolutional LSTM Network: A Machine Learning Approach for Precipitation Nowcasting” Publisher: arXiv Version Number: 2, 2015  DOI: 10.48550/ARXIV.1506.04214
  * [31] Xingjian Shi et al.  “Deep Learning for Precipitation Nowcasting: A Benchmark and A New Model” arXiv:1706.03458 [cs]  arXiv, 2017  URL: http://arxiv.org/abs/1706.03458
  * [32] Casper Kaae Sønderby et al.  “MetNet: A Neural Weather Model for Precipitation Forecasting” arXiv:2003.12140 [physics, stat]  arXiv, 2020  URL: http://arxiv.org/abs/2003.12140
  * [33] Zoltan Toth and Eugenia Kalnay  “Ensemble Forecasting at NCEP and the Breeding Method”  In _Monthly Weather Review_ 125.12, 1997, pp. 3297–3319  DOI: 10.1175/1520-0493(1997)125<3297:EFANAT>2.0.CO;2
  * [34] Kevin Trebing, Tomasz Stanczyk and Siamak Mehrkanoon  “SmaAt-UNet: Precipitation Nowcasting using a Small Attention-UNet Architecture” arXiv:2007.04417 [cs, eess]  arXiv, 2021  URL: http://arxiv.org/abs/2007.04417
  * [35] Zhengzhong Tu et al.  “MaxViT: Multi-Axis Vision Transformer” arXiv:2204.01697 [cs]  arXiv, 2022  URL: http://arxiv.org/abs/2204.01697
  * [36] Ashish Vaswani et al.  “Attention Is All You Need” arXiv:1706.03762 [cs]  arXiv, 2023  URL: http://arxiv.org/abs/1706.03762
  * [37] Yuchen Zhang et al.  “Skilful nowcasting of extreme precipitation with NowcastNet”  In _Nature_ 619.7970, 2023, pp. 526–532  DOI: 10.1038/s41586-023-06184-4