题目链接 题意：一棵树，给出n-1个边权，然后q组查询，每组查询询问两个点之间的距离。 思路：

dfs跑出根到每个点的距离，设为dis[i] 那么u,v两点的距离就是ans = dis[u]+dis[v]-2*dis[lca(u,v)];

转载自： 原文链接

树边，前向边，后向边，横叉边，应该说，不是一个图本身有的概念，应该是图进行DFS时才有的概念。图进行DFS会得到一棵DFS树（森林），在这个树上才有了这些概念。对图进行DFS，可以从任意的顶点开始，遍历的方式也是多样的，所以不同的遍历会得到不同的DFS树，进而产生不同的树边，前向边，后向边，横叉边。所以这4种边，是一个相对的概念。 在图的遍历中，往往设置了一个标记数组vis的bool值来记录顶点是否被访问过。但有些时候需要改变vis值的意义。令vis具有3种值并表示3种不同含义 vis = 0,表示该顶点没没有被访问 vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回 vis = …

1652: [Usaco2006 Feb]Treats for the Cows

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 290  Solved: 226 [Submit][Status][Discuss]

Description

FJ has purchased N (1 <= N <= 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he …

1651: [Usaco2006 Feb]Stall Reservations 专用牛棚

Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 700  Solved: 393 [Submit][Status][Discuss]

Description

Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= …

1650: [Usaco2006 Dec]River Hopscotch 跳石子

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 440  Solved: 290 [Submit][Status][Discuss]

Description

Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, …

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  Solved: 265 [Submit][Status][Discuss]

Description

The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget. The roller coaster will be built on a long linear stretch of land of length L (1 …

1648: [Usaco2006 Dec]Cow Picnic 奶牛野餐

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 562  Solved: 352 [Submit][Status][Discuss]

Description

The cows are having a picnic! Each of Farmer John's K (1 <= K <= 100) cows is grazing in one of N (1 <= N <= 1,000) pastures, conveniently numbered 1...N. The pastures …

1646: [Usaco2007 Open]Catch That Cow 抓住那只牛

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 915  Solved: 441 [Submit][Status][Discuss]

Description

Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 <= N <= 100,000) on a number line and the …

1644: [Usaco2007 Oct]Obstacle Course 障碍训练课

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 451  Solved: 226 [Submit][Status][Discuss]

Description

考虑一个 N x N (1 <= N <= 100)的有1个个方格组成的正方形牧场。有些方格是奶牛们不能踏上的，它们被标记为了'x'。例如下图：

1643: [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 330  Solved: 278 [Submit][Status][Discuss]

Description

农夫约翰已经从他的牧场中取得了数不清块数的正方形草皮，草皮的边长总是整数（有时农夫约翰割草皮的刀法不合适，甚至切出了边长为0的正方形草皮），他已经把草皮放在了一个奶牛贝茜已经知道的地方。 贝茜总是希望把美味的草皮放到她的秘密庄园里，她决定从这些草皮中取出恰好4块搬到她的秘密庄园中，然后把它们分成1×1的小块，组成一个面积 …