Gym 100796C Minimax Tree

dfs 編程能力 想法

傳送門：HustOJ

傳送門：CodeForce

題意

給出一棵n個(gè)節(jié)點(diǎn)的樹，有l(wèi)個(gè)葉節(jié)點(diǎn)，每個(gè)葉節(jié)點(diǎn)都有一個(gè)value值?，F(xiàn)有k個(gè)min標(biāo)簽，n-l-k個(gè)max標(biāo)簽，安排中間節(jié)點(diǎn)的標(biāo)簽，輸出根節(jié)點(diǎn)可能的最大值和最小值。min標(biāo)簽表示向上傳遞兒子中的最小值，max傳遞最大值。

思路

主要是dfs。 %%%1 %%%2

就最小值來講，要想讓某一個(gè)節(jié)點(diǎn)的值最終傳遞到根節(jié)點(diǎn)，它的祖先節(jié)點(diǎn)中必須全部采用min標(biāo)簽，最大值亦然。

然后這題想想就會(huì)發(fā)現(xiàn)就是dfs，每遞歸一層，層數(shù)lev就要加一，求出每個(gè)節(jié)點(diǎn)可能的最大值與最小值?；厮輹r(shí)根據(jù)當(dāng)前層數(shù)和標(biāo)簽數(shù)的關(guān)系寫入當(dāng)前節(jié)點(diǎn)的minmax值。

但是這樣會(huì)掛在test11。

然后需要注意到，如果一個(gè)節(jié)點(diǎn)只有一個(gè)孩子，那么他向上傳遞的值與標(biāo)簽無關(guān)。所以dfs時(shí)，如果一個(gè)節(jié)點(diǎn)只有一個(gè)孩子，那么遞歸進(jìn)他的孩子時(shí)lev數(shù)不加1就行了。

這是一個(gè)樣例，單步一下看看回溯時(shí)minval[5]的值就明白了。

8 2 1 2 3 4 5 5 1 0 0 0 0 0 1 10 5

代碼