題目描述

小強(qiáng)要在N個(gè)孤立的星球上建立起一套通信系統(tǒng)。這套通信系統(tǒng)就是連接N個(gè)點(diǎn)的一個(gè)樹(shù)。 這個(gè)樹(shù)的邊是一條一條添加上去的。在某個(gè)時(shí)刻，一條邊的負(fù)載就是它所在的當(dāng)前能夠 聯(lián)通的樹(shù)上路過(guò)它的簡(jiǎn)單路徑的數(shù)量。

題目的要求相當(dāng)于一個(gè)這條邊的兩個(gè)端點(diǎn)各自的子樹(shù)size乘起來(lái)。

?關(guān)鍵的函數(shù)為

void access(int x)

{

for (int y=0;x;y=x,x=fa[x])

{

splay(x);

xv[x]+=siz[ch[x][1]]; // 加上真實(shí)兒子的大小

ch[x][1]=y;

xv[x]-=siz[y];// splay 將去掉y這個(gè)兒子

}

}