Дарахти виртуалӣ / Дарахти ёрирасон
Дарахти бо қулла дода шудааст. дархостҳои шакли -ро коркард кунед. Барои ҳар як дархост ҷамъбасти масофаҳо барои ҳар як ҷуфт аз маҷмӯи додашудаи қуллаҳоро чоп кунед. Ба таври расмӣ, ёбед
ки дар он масофа (шумораи канорҳо) байни қуллаҳои ва мебошад.
Асосан, ҳамаи қуллаҳо ба маҷмӯа дохил мешаванд.
Ҳал хеле содда аст: саҳми ҳар як канорро ёфта, ба ҷавоб ҷамъ мекунем. Мураккабӣ аст.
Эзоҳ: ин инчунин барои канорҳои вазндор кор мекунад, агар ба ҷои вазнҳои канорро истифода барем.
Барои ҳолати умумӣ, мо Дарахти Виртуалӣ (Дарахти Ёрирасон)-ро ҷорӣ мекунем ва масъаларо ба ҳолати махсус дар дарахти хеле хурдтар табдил медиҳем.
Дарахти виртуалӣ барои маҷмӯи додашудаи маҷмӯи ҳаддиақали қуллаҳо мебошад, ки:
Ин маънои онро дорад, ки барои ҳар ду қуллаи , мо инчунин дорем.
Ҳамчун мисол, дарахти зеринро бо қулла баррасӣ кунед, ва фарз кунем, ки мо мехоҳем барои маҷмӯи дарахти виртуалӣ созем.
Барои сохтани Дарахти Ёрирасон, ки ба маҷмӯи мувофиқ аст:
tin) ҷудо кунед.lca-и онҳоро ба маҷмӯа илова кунед.Ин маҷмӯи ҳаддиақалро, ки нисбат ба LCA пӯшида аст, медиҳад ва мо метавонем дарахти виртуалиро бо мураккабии умумии созем.
Пас аз сохтани дарахти виртуалӣ, мо дархостро бо истифода аз саҳми канорҳо ҳал мекунем.
Барои канори дарахти виртуалӣ :
Пас ин канор ба ҷамъбаст аз рӯи ҷуфтҳои бебартиб чунин саҳм мегузорад:
Азбаски масъала ҷуфтҳои бо тартиб-ро мепурсад (ҳам ва ҳам ), ба зарб кунед:
Пас ба мо танҳо як DFS дар дарахти виртуалӣ лозим аст, то ҳамаи шуморишҳои зердарахтро ҳисоб кунем ва ҷавобро ҷамъ намоем.
Ин мураккабии умумиро барои ҳар як дархост дар сатҳи зерин нигоҳ медорад:
void VirtualTree(vector<int> v) {
// sort by DFS traversal order
sort(v.begin(), v.end(), [&](int x, int y) { return tin[x] < tin[y]; });
vector<int> s = v;
for (int i = 1; i < (int)v.size(); i++) {
s.push_back(lca(v[i], v[i - 1]));
}
sort(s.begin(), s.end(), [&](int x, int y) { return tin[x] < tin[y]; });
s.erase(unique(s.begin(), s.end()), s.end()); // delete duplicates
// build edges of the virtual tree using stack
vector<int> st = {s[0]};
for (int i = 1; i < (int)s.size(); i++) {
while (!st.empty() && !is_parent(st.back(), s[i])) {
st.pop_back();
}
add_edge(st.back(), s[i]);
st.push_back(s[i]);
}
}