Thank you for that extremely helpful post! Now my next question is, how do you do that off-chain. The whole point of going from A to B to C to D is that they are all connected to each other via previously opened payment channels. If you have to make a new address and thus a new payment channel which incorporates the hashed secret, then you have to make an on-chain transaction, and Alice might as well just open the channel directly with Dave, rather than going through Bob and Charlie.
The assumption here is that on-chain transactions are costly, and thus Alice greatly prefers to go through existing payment channels without needing to open another one.
So is there a way to use segwit to accomplish this with already opened channels?
I can require some information by having it be the solution to a separate input, and my own input is signed with SIGHASH_ALL locking that input requirement in... except that lightning channels require SIGHASH_NOINPUT.
What kind of payment channels are available where I can add a hash lock condition on an update to a pre-existing channel?
It doesn't have to be on-chain. The blockchain is only used in case of a dispute between the parties involved. In that example they say dave claims his payment by broadcasting a transaction on-chain and in doing so reveals the secret allowing bob to get paid too. But in practice dave would simply reveal the secret to bob off-chain and keep the payment channel open for future transactions.
Also you should read the official lightning docs section for HTLCs because it's a little more complicated than that in practice: