1806 . 你會寫 Tarjan 嗎？
TopCoder
Tags
Description
你，もも，解決了很多居民的煩惱之後，
他們推舉你出來選舉，
但是選舉並沒有那麼簡單，
並不是靠著老爸就可以。
而且這邊選制非常的特別，
是有很多基礎選區，中選區，大選區，加大選區，兩倍加大選區...構成的，
你發現不管在哪個地方，
只要贏得超過一半的支持就贏了，
你也發現，不管在哪，
總是奇數個選區，或者奇數個選民。
你想知道成為這邊的首領至少要拿到幾票。
Input Format
你發現你的野心越來越大，
所以你當上了二維空間的王就想當三維的王，
當了三維的王就想當四維的...
所以你有很多很多的選戰要打。
因此這題也是多筆測資，
第一個數字
接著測資的形式請參考Sample Input。
單行長度不超過 16384，每個小選區的人數不超過10000。
Output Format
對於每筆測資輸出你最少要贏幾票。
Sample Input 1
3 [[123][4567][89]] [[5][3][7][3][9]] [[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]
Sample Output 1
107 7 175
Hints
每個成對[]代表一個選區
[[123][4567][89]]
代表裡面有三個小選區
你在這三個小選區贏了其中兩個(也就是超過一半)就可以稱王了
如果選擇[123]跟[89]那麼會是最佳解。
贏得[123]需要贏62票，[89]需要45票，
所以最少票數是107票。
Problem Source
Tocknicsu
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |