分析
剛拿到這個題時看到可以更改信仰的宗教, 也就是可以改變路徑, 以為是動態樹的題目(動態樹不會), 後來發現都用的樹鏈剖分, 為每個宗教建立一個線段樹. 表示很神奇. 宗教數 <= 10^5, 每個宗教建立一個線段樹, 線段樹又一般開到四倍空間… 按我平常寫線段樹的方法肯定不行了. 於是從 HZWER 的博客裡學到了動態的線段樹, 需要訪問某結點時給它分配編號, 記錄結點的左右子結點編號而不是用o<<1表示o的左結點, o<<1^1表示o的右結點的方法. 有點指針的感覺. 一開始我卡在不知道怎麼修改信仰宗教上, 看 HZWER 發現很簡單, 把結點在最初信仰的宗教的線段樹裡的值修改為0, 再在改變後的信仰宗教的線段樹裡把值修改為原來的值. 這道題我調了很長時間, 直到最後發現一個最關鍵的錯誤出在查詢上.
以查詢和為例, 我一開始是這麼寫的 :
int ask_sum(int x, int y)
{
int ret = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y); // top
ret += query_sum(roots[c[x]], 1, n, tid[top[x]], tid[x]);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
ret += query_sum(roots[c[x]], 1, n, tid[x], tid[y]);
return ret;
}
這裡c[x]表示x城www.Bkjia.com市信仰的宗教, 當x改變時, c[x]勢必會改變, 但我們要查找的線段樹始終是不變的. 所以要記錄x最初的線段樹的根結點, 而不能每次都用roots[c[x]]來獲取.
改後 :
int ask_sum(int x, int y)
{
int ret = 0, cx = c[x]; // here
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y); // top
ret += query_sum(roots[cx], 1, n, tid[top[x]], tid[x]);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
ret += query_sum(roots[cx], 1, n, tid[x], tid[y]);
return ret;
}
發現vector存圖真的沒鄰接表好, 既費時間又費空間, 所以以後改用數組模擬鄰接表來存了.
