本题关联比赛
20160229

关于距离咨询的近10条评论(全部评论)
AntiLeaf 2017-05-25 15:56 14楼
练手，提供两种方法。 Fmuckss 2016-09-20 15:21 13楼
我只想说深夜写代码就是不行，de 和dee dfs时把m当n使了。。。难怪最后老出事残星誓言 2016-09-15 00:58 12楼
`if(deep[a]<deep[b]) Swap(a,b); if(deep[a]>deep[b]) for(int numstep=deep[a]-deep[b],j=0;numstep;numstep>>=1,j++) if(numstep&1) ans+=faw[a][j],a=fa[a][j];` 很好，这一段完美又写错了QAQ(话说deep的大于号小于号傻傻分不清楚) coolkid 2016-08-22 12:56 11楼
哒哒哒哒哒！ 2016-06-14 16:51 10楼
写的Tarjan常数好大啊，而且实现略有不足，方法并不是很好，但是注释还是很赞的 Marvolo 2016-05-24 20:37 9楼
不断地搞反top和n。。。 liu_runda 2016-05-08 07:25 8楼
0 2015-10-20 12:12 7楼
树上距离优美 Satoshi 2015-09-25 19:26 6楼
还傻逼的错误，ans+=f[x][j]+f[y][j]; x=fa[x][j]; y=fa[y][j];写反了，调了一晚上 forever 2015-07-28 21:52 5楼

1588. [USACO Feb04]距离咨询

★★ 输入文件：dquery.in 输出文件：dquery.out 简单对比
时间限制：1 s 内存限制：256 MiB

农夫约翰有$N$（$2<=N<=40000$）个农场，标号$1$到$N$。$M（2<=M<=40000）$条的不同的垂直或水平的道路连结着农场，道路的长度不超过$1000$.这些农场的分布就像下面的地图一样，图中农场用$F_1..F_7$表示：

每个农场最多能在东西南北四个方向连结$4$个不同的农场。此外，农场只处在道路的两端。道路不会交叉而且每对农场间有且仅有一条路径。邻居鲍伯要约翰来导航，但约翰丢了农场的地图，他只得从电脑的备份中修复率。每一条道路的信息如下：

从农场$23$往南经距离$10$到达农场$17$

从农场$1$往东经距离7到达农场$17$

. . .

最近美国过度肥胖非常普遍。农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松。马拉松路线要尽量长。

奶牛们拒绝跑马拉松，因为她们悠闲的生活无法承受约翰选择的如此长的赛道。因此约翰决心找一条更合理的赛道。他打算咨询你。读入地图之后会有$K$个问题，每个问题包括$2$个整数，就是约翰感兴趣的$2$个农场的编号，请尽快算出这$2$个农场间的距离。

第$1$行：两个分开的整数$N$和$M$。

第$2$到$M+1$行：每行包括$4$个分开的内容，$F_1,F_2,L,D$分别描述两个农场的编号，道路的长度，$F_1$到$F_2$的方向$N,E,S,W$。

第$2+M$行：一个整数$K（1<=K<=10000）$.

第$3+M$到$2+M+K$行：每行输入$2$个整数，代表$2$个农场。

对每个问题，输出单独的一个整数，给出正确的距离。

13
3
36

农场$2$到农场$6$有$20+3+13=36$的距离。

$Brian$ $Dean,2004$

$USACO$ $2004$ $February$ $Contest$ $Green$ $Problem$ $3$ $Distance$ $Queries$

$Translate$ $by:庄乐$