We carried out 13CO J=1-0, CS, and C34S J=2-1 and J=3-2 line observations of molecular clouds associated with 16 ultracompact (UC) HII regions with extended envelopes. The molecular clouds are the ones that give birth to rich stellar clusters and/or very massive (O7-O4) stars. Our data show that the clouds are very clumpy and of irregular morphology. They usually have much larger masses, velocity dispersions, and fractions of dense gas than molecular clouds that form early B or late O stars. This is compatible with earlier findings that more massive stars form in more massive cores. 13CO cores are in general associated with compact HII regions regardless of the presence of UC HII regions therein. In contrast, CS cores are preferentially associated with compact HII regions that contain UC HII regions. As with the fact that the compact HII regions containing UC HII regions are more compact than those not associated with UC HII regions, these indicate that the former may be in an earlier evolutionary phase than the latter. The diffuse extended envelopes of HII regions often develop in the direction of decreasing molecular gas density. Based on detailed comparison of molecular line data with radio continuum and recombination line data, the extended ionized envelopes are likely the results of champagne flows in at least 10 sources in our sample. Together these results appear to support a published suggestion that the extended emission around UC HII regions can be naturally understood by combining the champagne flow model with the hierarchical structure of molecular clouds. We discuss the implication of our results for the blister model of HII regions.