p,f,ne,c,b,d:
array[
0..
200010]
of longint; 2varfa:
array[
0..
100010,
0..
30]
of longint; 3var n,m,i,j,k,z,x,y:longint; 4varv:
array[
0..
100010]
of boolean; 5procedureadd(x,y,z:longint);//
建邻接表 6begin 7inc(m);c[m]:=z;b[m]:=y;ne[m]:=f[x];f[x]:=
m; 8end; 9functionlog(x:longint):longint;//
求log 10begin11exit(trunc(ln(x)/ln(
2))); 12end; 13procedure dfs(dep,num:longint); 14var j:longint; 15begin16j:=
f[num]; 17v[num]:=true;//
记录过则标记 18d[num]:=dep;//
记录深度 19whilej>
0do20begin21ifnotv[b[j]]
then//
没记录过的 22begin23p[b[j]]:=p[num]+c[j];//
更新距离 24dfs(dep+
1,b[j]);fa[b[j],
0]:=num;//
fa[i,j]指i的2^j倍祖先 25end; 26j:=
ne[j]; 27end; 28end; 29function lca(x,y:longint):longint; 30var t,i,j,k:longint; 31begin32ifd[x]
来源: