新坑_(:зゝ∠)_
补作业ing
进度:3/5
BZOJ 1787: [Ahoi2008]Meet 紧急集合:
题意:给定树上的三个点,求一个点使得三个点到该点的路径和最短。
设三点为x,y,z,k1=lca(x,y),k2=lca(x,z),k3=lca(y,z);
由lca(lca(x,y),z)唯一,可知k1,k2,k3中必定有两个相等。考虑实际意义可得,相同的lca节点总路程必定长于剩余的lca节点总路程。(差为两个lca节点的路径长度)
∴剩余的lca节点即所求节点。路径和求出lca(原节点,ans节点)后dfs即可。
BZOJ 1602: [Usaco2008 Oct]牧场行走:
把上面一题最后一步求路径和做一遍就可以了2333.
BZOJ 1699: [Usaco2007 Jan]Balanced Lineup排队
怎么搞都可以程度的RBQ...不...RMQ.
评论