1. 题目
最长链
【问题描述】
给定一棵有N个节点的树,求每个节点到其他节点的最大距离
【输入格式】
输入第一行是一个自然数 N (N<=1 0000), 接下来 (N-1) 行描述:
第i行包含两个自然数 , 表示编号为i的节点连接到的节点编号和这条网线的长度..距离总长不会超过10^9. 每行中的两个数字用空格隔开.
【输出格式】
输出包含N行. 第i行表示对于离编号为i的节点最远的节点与该节点的距离Si(1<=i<=N).
【样例输入】length.in
3
1 1
1 2
【样例输出】length.out
2
3
3
【数据范围】
30% N<=100
100%N<=10000
2. 题目实质
这个题目写得很明白,略。
3. 算法
关于这个题,有一种很特立独行的算法。
首先说明一个定理,离树中某一个点最远的点,一定是在树的直径(树中距离最远的两个点之间的路径)的一个端点。
证明:如果存在一个更远的点,不是端点,但是比较远的那个端点距离这个点更远,则此时,距离这个点较近的那个端点可以经过这个点,到达那个更远的点,这样就会找出一条比直径更长的路径。但事实上,直径应该是一个树中最长的路径,所以离树中某一个点最远的点,一定是在树的直径(树中距离最远的两个点之间的路径)的一个端点,证毕。
然后,这样的话,就可以先求出树的直径的两个端点(从任意一个点开始 BFS ,找到距离他最远的那个点,根据上方定理,这必是一个端点,再从这个已知端点开始 BFS ,找到距离他最远的那个点,显然这就是另一个端点),然后从这两个点开始,走单源最短路。然后求解的时候,只需要找出每一个点距这两个点的距离中的较大的那个,就是答案了。
然后这个题的标准算法是树形动规。
这个方法太麻烦,而且这是个多叉树,存都不好存,本人没有深入研究,在此引用一下。
1.题目可以使用搜索做,但是由于数据范围极大,极可能会超时 |
2.这样就可以向其他方面思考:题目中给出的是一棵树,就是树形DP吧 |
距离一个节点最远的点 在此节点的子树中 或 在它的父节点的其他子树中 |
这样,每一个节点要存储三个信息: |
1.在他的子树中离他最远的点到他的距离 |
2.在他的子树中离他第二远的点到他的距离 |
3.在他的祖先及其出了他本身的子树中里他最远的点到他的距离 |
假设F[i][0]是在以i为根的子树的点里离i最远的距离 |
F[i][2]是不在以i为根的子树的点离i最远的距离 |
显然答案是max(F[i][0] , F[i][2]) |
第一种显然一次dfs就搞定了 |
而第二个不是很好办.. |
所以我们分析一下..得到了这个方程 |
F[i][2] = max(F[Parent[i]][2] , F[Parent[i]][0]) + Dist[Parent[i]][i]; |
不过显然当如果F[Parent[i]][0]的决策是i的时候是错的..所以我们只要再记 |
录一个“在以i为根的子树里且第一步决策和F[i][0]不同的点离i的最大值”令其为F[i][1] |
if(F[Parent[i]][0] == F[i][0] + Dist[Parent[i]][i]) |
F[i][2] = max(F[Parent[i]][2] , F[Parent[i]][1]) + Dist[Parent[i]][i]; |
Else F[i][2] = max(F[Parent[i]][2] , F[Parent[i]][0]) + Dist[Parent[i]][i]; |
4. 代码
特殊算法 (Leve)
type pointer=^rec;
rec=record
num,len:longint;
next:pointer;
end;
var
i,j,a1,a2,n,x,y,max:longint;
link:array[1..10000] of pointer;
d1,d2:array[1..10000] of longint;
v:array[1..10000] of boolean;
q:array[1..1000000] of longint;
p:pointer;
procedure spfa1(x:longint);
var
i,l,r,temp:longint;
p:pointer;
begin
filldword(d1,sizeof(d1)>>2,maxlongint>>1);
fillchar(v,sizeof(v),false);
d1[x]:=0;
v[x]:=true;
q[1]:=x;
l:=0; r:=1;
while l<r do
begin
inc(l);
temp:=q[l];
p:=link[temp];
v[temp]:=false;
while p<>nil do
begin
if d1[p^.num]>d1[temp]+p^.len then
begin
d1[p^.num]:=d1[temp]+p^.len;
if not v[p^.num] then
begin
v[p^.num]:=true;
inc(r);
q[r]:=p^.num;
end;
end;
p:=p^.next;
end;
end;
end;
procedure spfa2(x:longint);
var
i,l,r,temp:longint;
p:pointer;
begin
filldword(d2,sizeof(d2)>>2,maxlongint>>1);
fillchar(v,sizeof(v),false);
d2[x]:=0;
v[x]:=true;
q[1]:=x;
l:=0; r:=1;
while l<r do
begin
inc(l);
temp:=q[l];
p:=link[temp];
v[temp]:=false;
while p<>nil do
begin
if d2[p^.num]>d2[temp]+p^.len then
begin
d2[p^.num]:=d2[temp]+p^.len;
if not v[p^.num] then
begin
v[p^.num]:=true;
inc(r);
q[r]:=p^.num;
end;
end;
p:=p^.next;
end;
end;
end;
begin
assign(input,'length.in');
assign(output,'length.out');
reset(input);
rewrite(output);
readln(n);
for i:=2 to n do
begin
read(x,y);
new(p);
p^.num:=x;
p^.len:=y;
p^.next:=link[i];
link[i]:=p;
new(p);
p^.num:=i;
p^.len:=y;
p^.next:=link[x];
link[x]:=p;
end;
spfa1(1);
max:=0;
for i:=1 to n do
if d1[i]<maxlongint>>1 then
if d1[i]>max then
begin
max:=d1[i];
a1:=i;
end;
spfa1(a1);
max:=0;
for i:=1 to n do
if d1[i]<maxlongint>>1 then
if d1[i]>max then
begin
max:=d1[i];
a2:=i;
end;
spfa2(a2);
for i:=1 to n do
begin
if d1[i]=maxlongint>>1 then d1[i]:=0;
if d2[i]=maxlongint>>1 then d2[i]:=0;
end;
for i:=1 to n do
if d1[i]>d2[i] then
writeln(d1[i])
else
writeln(d2[i]);
close(input);
close(output);
end.
树形动规 (std)
program length;
type
edge=record
x,w,next:longint;
end;
var
e,e2:array[0..200000]of edge;
k,k2:array[0..10000]of longint;
fa:array[0..10000]of longint;
w:array[0..10000]of longint;
tot,tot2,i,j,n,x,y:longint;
v:array[0..10000]of boolean;
f:array[0..10000,0..2]of longint;
function max(a,b:longint):longint;
begin
if (a>b) then exit(a) else exit(b);
end;
procedure add2(a,b,c:longint);
begin
inc(tot2);
e2[tot2].x:=b;
e2[tot2].w:=c;
e2[tot2].next:=k2[a];
k2[a]:=tot2;
end;
procedure add(a,b,c:longint);
begin
inc(tot);
e[tot].x:=b;
e[tot].w:=c;
e[tot].next:=k[a];
k[a]:=tot;
end;
procedure build(x:longint);
var
t:longint;
begin
v[x]:=true;
t:=k2[x];
while (t<>0) do
begin
if (not v[e2[t].x]) then
begin
fa[e2[t].x]:=x;
w[e2[t].x]:=e2[t].w;
add(x,e2[t].x,e2[t].w);
build(e2[t].x);
end;
t:=e2[t].next;
end;
end;
procedure dp_down(x:longint);
var
t:longint;
begin
t:=k[x];
while (t<>0) do
begin
dp_down(e[t].x);
if (f[e[t].x][1]+e[t].w>f[x][1]) then
begin
f[x][2]:=f[x][1];
f[x][1]:=f[e[t].x][1]+e[t].w;
end
else
if (f[e[t].x][1]+e[t].w>f[x][2]) then
begin
f[x][2]:=f[e[t].x][1]+e[t].w;
end;
t:=e[t].next;
end;
end;
procedure dp_up(x:longint);
var
t:longint;
begin
if (fa[x]<>0) then
begin
if (f[fa[x]][1]=f[x][1]+w[x]) then
f[x][0]:=max(f[fa[x]][2],f[fa[x]][0])+w[x]
else f[x][0]:=max(f[fa[x]][1],f[fa[x]][0])+w[x];
end;
t:=k[x];
while (t<>0) do
begin
dp_up(e[t].x);
t:=e[t].next;
end;
end;
begin
assign(input,'length.in');reset(input);
assign(output,'length.out');rewrite(output);
readln(n);
for i:=2 to n do
begin
readln(x,y);
add2(i,x,y);
add2(x,i,y);
end;
build(1);
dp_down(1);
dp_up(1);
for i:=1 to n do
begin
writeln(max(f[i][0],f[i][1]));
end;
close(input);
close(output);
end.