While regulatory T (Treg) cells are traditionally viewed as professional suppressors of antigen presenting cells and effector T cells in both autoimmunity and cancer, recent findings of distinct Treg cell functions in tissue maintenance suggest that their regulatory purview extends to a wider range of cells and is broader than previously assumed. To elucidate tumoral Treg cell 'connectivity' to diverse tumor-supporting accessory cell types, we explored immediate early changes in their single-cell transcriptomes upon punctual Treg cell depletion in experimental lung cancer and injury-induced inflammation. Before any notable T cell activation and inflammation, fibroblasts, endothelial and myeloid cells exhibited pronounced changes in their gene expression in both cancer and injury settings. Factor analysis revealed shared Treg cell-dependent gene programs, foremost, prominent upregulation of VEGF and CCR2 signaling-related genes upon Treg cell deprivation in either setting, as well as in Treg cell-poor versus Treg cell-rich human lung adenocarcinomas. Accordingly, punctual Treg cell depletion combined with short-term VEGF blockade showed markedly improved control of PD-1 blockade-resistant lung adenocarcinoma progression in mice compared to the corresponding monotherapies, highlighting a promising factor-based querying approach to elucidating new rational combination treatments of solid organ cancers.