首页 > 代码库 > BZOJ1602: [Usaco2008 Oct]牧场行走

BZOJ1602: [Usaco2008 Oct]牧场行走

2024-07-17 01:18:38   224人阅读

1602: [Usaco2008 Oct]牧场行走

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 1084  Solved: 556
[Submit][Status]

Description

N头牛（2<=n<=1000）别人被标记为1到n，在同样被标记1到n的n块土地上吃草，第i头牛在第i块牧场吃草。 这n块土地被n-1条边连接。 奶牛可以在边上行走，第i条边连接第Ai，Bi块牧场，第i条边的长度是Li（1<=Li<=10000）。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算Q(1<=q<=1000)对奶牛之间的距离。

Input

*第一行：两个被空格隔开的整数：N和Q

 *第二行到第n行：第i+1行有两个被空格隔开的整数：AI，BI，LI

*第n+1行到n+Q行：每一行有两个空格隔开的整数：P1，P2，表示两头奶牛的编号。

Output

*第1行到第Q行：每行输出一个数，表示那两头奶牛之间的距离。

Sample Input

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

Sample Output

2
7

HINT

 

Source

资格赛

题解：
不想写倍增了，把树链剖分的代码贴上改了改就A了。。。
每个节点保存的是到父亲的距离，所以对LCA要特判
代码：
  1 const maxn=1000+100;  2 type node1=record  3      go,next,z:longint;  4      end;  5      node2=record  6      l,r,mid,sum:longint;  7      end;  8   9 var  e:array[0..2*maxn] of node1; 10      t:array[0..4*maxn] of node2; 11      p,a,v,fa,s,head,dep,son,top:array[0..maxn] of longint; 12      i,n,m,x,y,z,sz,ans,tot:longint; 13      ch:char; 14      procedure swap(var x,y:longint); 15       var t:longint; 16       begin 17         t:=x;x:=y;y:=t; 18       end; 19      procedure insert(x,y,z:longint); 20       begin 21         inc(tot); 22         e[tot].go:=y;e[tot].z:=z;e[tot].next:=head[x];head[x]:=tot; 23       end; 24      function min(x,y:longint):longint; 25       begin 26         if x<y then exit(x) else exit(y); 27       end; 28      function max(x,y:longint):longint; 29       begin 30         if x>y then exit(x) else exit(y); 31       end; 32  33 procedure dfs1(x:longint); 34  var i,j,y:longint; 35  begin 36    j:=0;s[x]:=1; 37    i:=head[x]; 38    while i<>0 do 39     begin 40      y:=e[i].go; 41      if dep[y]=0 then 42       begin 43         dep[y]:=dep[x]+1; 44         fa[y]:=x;v[y]:=e[i].z; 45         dfs1(y); 46         inc(s[x],s[y]); 47         if s[y]>s[j] then j:=y; 48       end; 49      i:=e[i].next; 50     end; 51    son[x]:=j; 52  end; 53 procedure dfs2(x,chain:longint); 54  var i,y:longint; 55  begin 56    inc(sz);p[x]:=sz;top[x]:=chain; 57    if son[x]<>0 then dfs2(son[x],chain); 58    i:=head[x]; 59    while i<>0 do 60      begin 61       y:=e[i].go; 62       if (p[y]=0) and (y<>son[x]) then dfs2(y,y); 63       i:=e[i].next; 64      end; 65  end; 66 procedure pushup(k:longint); 67  begin 68     t[k].sum:=t[k<<1].sum+t[k<<1+1].sum; 69  end; 70  71 procedure build(k,x,y:longint); 72  begin 73    with t[k] do 74     begin 75      l:=x;r:=y;mid:=(l+r)>>1; 76      if l=r then begin sum:=a[l];exit;end; 77      build(k<<1,l,mid);build(k<<1+1,mid+1,r); 78      pushup(k); 79     end; 80  end; 81 function getsum(k,x,y:longint):longint; 82  begin 83    with t[k] do 84     begin 85      if (l=x) and (r=y) then exit(sum); 86      if y<=mid then exit(getsum(k<<1,x,y)) 87      else if x>mid then exit(getsum(k<<1+1,x,y)) 88      else exit(getsum(k<<1,x,mid)+getsum(k<<1+1,mid+1,y)); 89     end; 90  end; 91 procedure init; 92  begin 93    readln(n,m); 94    for i:=1 to n-1 do begin readln(x,y,z);insert(x,y,z);insert(y,x,z);end; 95    dep[1]:=1; 96    dfs1(1); 97    dfs2(1,1); 98    for i:=2 to n do a[p[i]]:=v[i]; 99    build(1,1,n);100  end;101 procedure solvesum;102  begin103    ans:=0;104    readln(x,y);105      while top[x]<>top[y] do106      begin107       if dep[top[x]]<dep[top[y]] then swap(x,y);108       inc(ans,getsum(1,p[top[x]],p[x]));109       x:=fa[top[x]];110      end;111    if dep[x]>dep[y] then swap(x,y);112    inc(ans,getsum(1,p[x],p[y]));113    if p[x]<>1 then dec(ans,v[x]);114    writeln(ans);115  end;116 117 procedure main;118  begin119    for i:=1 to m do solvesum;120  end;121 122 begin123   assign(input,‘input.txt‘);assign(output,‘output.txt‘);124   reset(input);rewrite(output);125   init;126   main;127   close(input);close(output);128 end.
View Code

 

 


联系
我们