  Given two strings of length $n$ over alphabet $\Sigma$, and an upper bound
$k$ on their edit distance, the algorithm of Myers (Algorithmica'86) and Landau
and Vishkin (JCSS'88) computes the unweighted string edit distance in
$\mathcal{O}(n+k^2)$ time. Till date, it remains the fastest algorithm for
exact edit distance computation, and it is optimal under the Strong Exponential
Hypothesis (STOC'15). Over the years, this result has inspired many
developments, including fast approximation algorithms for string edit distance
as well as similar $\tilde{\mathcal{O}}(n+$poly$(k))$-time algorithms for
generalizations to tree and Dyck edit distances. Surprisingly, all these
results hold only for unweighted instances.
  While unweighted edit distance is theoretically fundamental, almost all
real-world applications require weighted edit distance, where different weights
are assigned to different edit operations and may vary with the characters
being edited. Given a weight function $w: \Sigma \cup \{\varepsilon \}\times
\Sigma \cup \{\varepsilon \} \rightarrow \mathbb{R}_{\ge 0}$ (such that
$w(a,a)=0$ and $w(a,b)\ge 1$ for all $a,b\in \Sigma \cup \{\varepsilon\}$ with
$a\ne b$), the goal is to find an alignment that minimizes the total weight of
edits. Except for the vanilla $\mathcal{O}(n^2)$-time dynamic-programming
algorithm and its almost trivial $\mathcal{O}(nk)$-time implementation, none of
the aforementioned developments on the unweighted edit distance apply to the
weighted variant. In this paper, we propose the first
$\mathcal{O}(n+$poly$(k))$-time algorithm that computes weighted string edit
distance exactly, thus bridging a fundamental gap between our understanding of
unweighted and weighted edit distance. We then generalize this result to
weighted tree and Dyck edit distances, which lead to a deterministic algorithm
that improves upon the previous work for unweighted tree edit distance.
