1.        题目

幸福的道路(race)

【问题描述】

小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.

他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.

他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).

 

【输入格式】

第一行包含一个整数N.

第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.

 

【输出格式】

 

每天的锻炼路径长度

【样例输入】

3 

1 1

1 3

 

【样例输出】

3

4

4

 

数据范围：

 

50%的数据N<=1000

80%的数据N<=100 000

100%的数据N<=1000 000

 

2.        算法

第一种方法：用队列优化的树形动规。

 

还有一种比较纠结的，以前在博客中写过：

首先说明一个定理，离树中某一个点最远的点，一定是在树的直径（树中距离最远的两个点之间的路径）的一个端点。

证明：如果存在一个更远的点，不是端点，但是比较远的那个端点距离这个点更远，则此时，距离这个点较近的那个端点可以经过这个点，到达那个更远的点，这样就会找出一条比直径更长的路径。但事实上，直径应该是一个树中最长的路径，所以离树中某一个点最远的点，一定是在树的直径（树中距离最远的两个点之间的路径）的一个端点，证毕。

然后，这样的话，就可以先求出树的直径的两个端点（从任意一个点开始  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.

 

 

PS：这是这个题的化简版，原题：

       

【问题描述】

 

小T与小L终于决定走在一起,他们不想浪费在一起的每一分每一秒,所以他们决定每天早上一同晨练来享受在一起的时光.

 

他们画出了晨练路线的草图,眼尖的小T发现可以用树来描绘这个草图.

 

他们不愿枯燥的每天从同一个地方开始他们的锻炼,所以他们准备给起点标号后顺序地从每个起点开始(第一天从起点一开始,第二天从起点二开始……). 而且他们给每条道路定上一个幸福的值.很显然他们每次出发都想走幸福值和最长的路线(即从起点到树上的某一点路径中最长的一条).

 

他们不愿再经历之前的大起大落,所以决定连续几天的幸福值波动不能超过M(即一段连续的区间并且区间的最大值最小值之差不超过M).他们想知道要是这样的话他们最多能连续锻炼多少天(hint:不一定从第一天一直开始连续锻炼)?

 

现在，他们把这个艰巨的任务交给你了!

 

 

 

【输入格式】

 

第一行包含两个整数N, M(M<=10^9).

 

第二至第N行,每行两个数字Fi , Di, 第i行表示第i个节点的父亲是Fi,且道路的幸福值是Di.

 

 

 

【输出格式】

 

最长的连续锻炼天数

 

 

 

【样例输入】

 

3 2

 

1 1

 

1 3

 

 

 

【样例输出】

 

3

 

 

 

数据范围：

 

 

 

50%的数据N<=1000

 

80%的数据N<=100000

 

100%的数据N<=1000 000

 

 

然后，求出来每天锻炼路径之后，最长连续锻炼天数怎么快速的求出来。。。。才疏学浅，三个点超时。

这是那个 70 的代码。。。。写得好烂。。。。

代码：（SueMiller）

program ACRush;

var a:array[0..2000010,1..3]of longint;

    dist1,dist2,dist3:array[0..1000010]of longint;

    t,arr:array[0..1000010]of longint;

    q:array[0..10000010]of longint;

    vq:array[0..1000010]of boolean;

    i,j,k,d1,d2:longint;

    n,m,tot,maxx,minn,l,r,ans,tempn,tempx:longint;

procedure quicksort(l,r:longint);

var x,i,j:longint;

begin

 i:=l; j:=r; x:=a[(l+r)>>1,1];

 repeat

  while a[i,1]<x do inc(i);

  while x<a[j,1] do dec(j);

  if i<=j then

   begin

   a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];

   inc(i); dec(j);

   end;

 until i>j;

 if l<j then quicksort(l,j);

 if i<r then quicksort(i,r);

end;

procedure spfa1(x:longint);

begin

  l:=0;

  r:=1;

  q[1]:=x;

  filldword(dist1,sizeof(dist1)>>2,maxlongint>>1);

  dist1[x]:=0;

  fillchar(vq,sizeof(vq),false);

  vq[x]:=true;

  while l<r do

    begin

      inc(l);

      for i:=t[q[l]] to tot do

        if a[i,1]<>q[l] then break

        else

          begin

            if dist1[q[l]]+a[i,3]<dist1[a[i,2]] then

              begin

                dist1[a[i,2]]:=dist1[q[l]]+a[i,3];

                if not vq[a[i,2]] then

                  begin

                    inc(r);

                    q[r]:=a[i,2];

                    vq[a[i,2]]:=true;

                  end;

              end;

          end;

      vq[q[l]]:=false;

    end;

end;

procedure spfa2(x:longint);

begin

  l:=0;

  r:=1;

  q[1]:=x;

  filldword(dist2,sizeof(dist2)>>2,maxlongint>>1);

  dist2[x]:=0;

  fillchar(vq,sizeof(vq),false);

  vq[x]:=true;

  while l<r do

    begin

      inc(l);

      for i:=t[q[l]] to tot do

        if a[i,1]<>q[l] then break

        else

          begin

            if dist2[q[l]]+a[i,3]<dist2[a[i,2]] then

              begin

                dist2[a[i,2]]:=dist2[q[l]]+a[i,3];

                if not vq[a[i,2]] then

                  begin

                    inc(r);

                    q[r]:=a[i,2];

                    vq[a[i,2]]:=true;

                  end;

              end;

          end;

      vq[q[l]]:=false;

    end;

end;

procedure spfa3(x:longint);

begin

  l:=0;

  r:=1;

  q[1]:=x;

  filldword(dist3,sizeof(dist3)>>2,maxlongint>>1);

  dist3[x]:=0;

  fillchar(vq,sizeof(vq),false);

  vq[x]:=true;

  while l<r do

    begin

      inc(l);

      for i:=t[q[l]] to tot do

        if a[i,1]<>q[l] then break

        else

          begin

            if dist3[q[l]]+a[i,3]<dist3[a[i,2]] then

              begin

                dist3[a[i,2]]:=dist3[q[l]]+a[i,3];

                if not vq[a[i,2]] then

                  begin

                    inc(r);

                    q[r]:=a[i,2];

                    vq[a[i,2]]:=true;

                  end;

              end;

          end;

      vq[q[l]]:=false;

    end;

end;

function max(x,y:longint):longint;

begin

  if x>y then exit(x) else exit(y);

end;

begin

  assign(input,'race.in');reset(input);

  assign(output,'race.out');rewrite(output);

  readln(n,m);

  for i:=1 to n-1 do

    begin

      readln(j,k);

      inc(tot);

      a[tot,1]:=i+1;

      a[tot,2]:=j;

      a[tot,3]:=k;

      inc(tot);

      a[tot,1]:=j;

      a[tot,2]:=i+1;

      a[tot,3]:=k;

    end;

  quicksort(1,tot);

  t[a[1,1]]:=1;

  for i:=2 to tot do

    if a[i,1]<>a[i-1,1] then t[a[i,1]]:=i;

  spfa1(1);

  d1:=0;

  k:=0;

  for i:=1 to n do

    if dist1[i]>k then

      begin

        k:=dist1[i];

        d1:=i;

      end;

  spfa2(d1);

  d2:=0;

  k:=0;

  for i:=1 to n do

    if dist2[i]>k then

      begin

        k:=dist2[i];

        d2:=i;

      end;

  spfa3(d2);

  for i:=1 to n do

    arr[i]:=max(dist2[i],dist3[i]);

  ans:=1;

  for i:=1 to n do

    begin

      l:=i;

      r:=i;

      maxx:=arr[i];

      minn:=arr[i];

      tempn:=arr[i]+1;

      tempx:=arr[i]-1;

      while maxx-minn<=m do

        begin

          dec(l);

          if l=0 then break;

          if arr[l]<minn then

            begin

              tempn:=minn;

              minn:=arr[l];

            end

          else

            if arr[l]<tempn then tempn:=arr[l];

          if arr[l]>maxx then

            begin

              tempx:=maxx;

              maxx:=arr[l];

            end

          else

            if arr[l]>tempx then tempx:=arr[l];

        end;

      if l<>0 then

        begin

          if arr[l]=maxx then maxx:=tempx;

          if arr[l]=minn then minn:=tempn;

        end;

      inc(l);

      while maxx-minn<=m do

        begin

          inc(r);

          if r>n then break;

          if arr[r]<minn then

            begin

              tempn:=minn;

              minn:=arr[r];

            end

          else

            if arr[r]<tempn then tempn:=arr[r];

          if arr[r]>maxx then

            begin

              tempx:=maxx;

              maxx:=arr[r];

            end

          else

            if arr[r]>tempx then tempx:=arr[r];

        end;

      if r<>n+1 then

        begin

          if arr[r]=maxx then maxx:=tempx;

          if arr[r]=minn then minn:=tempn;

        end;

      dec(r);

      if r-l+1>ans then ans:=r-l+1;

      if ans=n then break;

 

      l:=i;

      r:=i;

      maxx:=arr[i];

      minn:=arr[i];

      tempn:=arr[i]+1;

      tempx:=arr[i]-1;

      while maxx-minn<=m do

        begin

          inc(r);

          if r>n then break;

          if arr[r]<minn then

            begin

              tempn:=minn;

              minn:=arr[r];

            end

          else

            if arr[r]<tempn then tempn:=arr[r];

          if arr[r]>maxx then

            begin

              tempx:=maxx;

              maxx:=arr[r];

            end

          else

            if arr[r]>tempx then tempx:=arr[r];

        end;

      if r<>n+1 then

        begin

          if arr[r]=maxx then maxx:=tempx;

          if arr[r]=minn then minn:=tempn;

        end;

      dec(r);

      while maxx-minn<=m do

        begin

          dec(l);

          if l=0 then break;

          if arr[l]<minn then

            begin

              tempn:=minn;

              minn:=arr[l];

            end

          else

            if arr[l]<tempn then tempn:=arr[l];

          if arr[l]>maxx then

            begin

              tempx:=maxx;

              maxx:=arr[l];

            end

          else

            if arr[l]>tempx then tempx:=arr[l];

        end;

      if l<>0 then

        begin

          if arr[l]=maxx then maxx:=tempx;

          if arr[l]=minn then minn:=tempn;

        end;

      inc(l);

      if r-l+1>ans then ans:=r-l+1;

      if ans=n then break;

    end;

  writeln(ans);

  close(input);close(output);

end.