题目描述

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。

题目的要求相当于一个这条边的两个端点各自的子树size乘起来。

 关键的函数为

void access(int x)

{

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

{

splay(x);

xv[x]+=siz[ch[x][1]]; // 加上真实儿子的大小

ch[x][1]=y;

xv[x]-=siz[y];// splay 将去掉y这个儿子

}

}