The lack of large and diverse discourse treebanks hinders the application of\ndata-driven approaches, such as deep-learning, to RST-style discourse parsing.\nIn this work, we present a novel scalable methodology to automatically generate\ndiscourse treebanks using distant supervision from sentiment-annotated\ndatasets, creating and publishing MEGA-DT, a new large-scale\ndiscourse-annotated corpus. Our approach generates discourse trees\nincorporating structure and nuclearity for documents of arbitrary length by\nrelying on an efficient heuristic beam-search strategy, extended with a\nstochastic component. Experiments on multiple datasets indicate that a\ndiscourse parser trained on our MEGA-DT treebank delivers promising\ninter-domain performance gains when compared to parsers trained on\nhuman-annotated discourse corpora.\n