关键词：
3363: [Usaco2004 Feb]Cow Marathon 奶牛马拉松
Description
? 最近美国过度肥胖非常普遍，农夫约翰为了让他的奶牛多做运动，举办了奶牛马拉松．马拉
松路线要尽量长，所以，告诉你农场的地图（该地图的描述与上题一致），请帮助约翰寻找两个
最远农场间的距离．
Input
? 第1行：两个分开的整数N和M.
? 第2到M+1行：每行包括4个分开的内容，Fi，F2，L，D分别描述两个农场的编号，道路的长
度，F1到F2的方向N，E，S，W．
Output
? 一个整数，表示最远两个衣场间的距离．
找树的直径，水。
m和opt都是没有用的。
code
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int wx=500017;
inline int read()
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9')if(ch=='-')f=-1;ch=getchar();
while(ch>='0'&&ch<='9')sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();
return sum*f;
struct e
int nxt,to,dis;
edge[wx];
int n,m,k,num;
int ans,maxn,pos;
int head[wx],dis[wx];
void add(int from,int to,int dis)
edge[++num].nxt=head[from];
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
void dfs(int u,int fa)
for(int i=head[u];i;i=edge[i].nxt)
int v=edge[i].to;
if(v==fa)continue;
dis[v]=dis[u]+edge[i].dis;
dfs(v,u);
int main()
n=read();read();
for(int i=1;i<n;i++)
int x,y,z;
x=read();y=read();z=read();scanf("%s");
add(x,y,z);add(y,x,z);
dfs(1,0);
for(int i=1;i<=n;i++)
if(maxn<dis[i])
maxn=dis[i];pos=i;
memset(dis,0,sizeof dis);
dfs(pos,0);
for(int i=1;i<=n;i++)
ans=max(ans,dis[i]);
printf("%d
",ans);
return 0;
bzoj3362/3363/3364/3365[usaco2004feb]树上问题杂烩并查集/树形dp/lca/树的点分治
题目描述农夫约翰有N(2≤N≤40000)个农场，标号1到N,M(2≤M≤40000)条的不同的垂直或水平的道路连结着农场，道路的长度不超过1000.这些农场的分布就像下面的地图一样，图中农场用F1..F7表示, 每个农场最多能在东西南北四个方... 查看详情
bzoj3363poj1985cowmarathon树的直径
...目大意：给出一棵树。求两点间的最长距离。思路：裸地树的直径。两次BFS，第一次随便找一个点宽搜。然后用上次宽搜时最远的点在宽搜。得到的最长距离就是树的直径。CODE：#include<queue>#include<cstdio>#include<cstring>... 查看详情
bzoj3364:[usaco2004feb]distancequeries距离咨询
Description一棵树,询问两点间距离.Sol倍增.方向没用.没有然后了.Code/**************************************************************Problem:3364User:BeiYuLanguage:C++Result:AcceptedTime:400msMemory:11556kb******************** 查看详情
bzoj3367[usaco2004feb]thebiggame球赛*
bzoj3367[Usaco2004Feb]TheBigGame球赛题意：n只奶牛，每只支持两个球队中的一个，它们依次上车，上到一定程度可以开走这辆车并换下一辆继续上。要求一辆车上支持不同球队的奶牛数的差≤I，或者这辆车上只有支持同一球队的牛。... 查看详情
bzoj3362:[usaco2004feb]navigationnightmare导航噩梦
Description给你每个点与相邻点的距离和方向,求两点间的曼哈顿距离.(nleqslant4 imes10^4).Sol加权并查集.像向量合成一样合并就可以了,找(f[x])的时候需要先记录现在的父节点,然后更新他新的父节点.Code/*******************************************... 查看详情
bzoj3365:[usaco2004feb]distancestatistics路程统计
Description一棵树,统计距离不大于(k)的点对个数.Sol点分治.发现自己快把点分治忘干净了...找重心使所有儿子的最大值尽量小,然后每次处理全部子树,再减去每个子树的贡献,这样就得到子树间的贡献了,然后再搞子树就可以,这就是... 查看详情
bzoj_3362_[usaco2004feb]navigationnightmare导航噩梦_并查集
BZOJ_3362_[Usaco2004Feb]NavigationNightmare导航噩梦_并查集Description 农夫约翰有N(2≤N≤40000)个农场，标号1到N,M(2≤M≤40000)条的不同的垂直或水平的道路连结着农场，道路的长度不超过1000.这些农场的分布就像下面的地... 查看详情
bzoj1468:tree&bzoj3365:[usaco2004feb]distancestatistics路程统计(代码片段)
【传送门：BZOJ1468&BZOJ3365】简要题意： 给出一棵n个点的树，和每条边的边权，求出有多少个点对的距离<=k题解： 点分治模板题 点分治的主要步骤： 1、首先选取一个点，把无根树变成有根树。那么如何选点... 查看详情
刷题bzoj3365[usaco2004feb]distancestatistics路程统计(代码片段)
Description在得知了自己农场的完整地图后（地图形式如前三题所述），约翰又有了新的问题．他提供一个整数K(1≤K≤109)，希望你输出有多少对农场之间的距离是不超过K的．Input第1到I+M行：与前三题相同；第M+2行：一个整数K.Outpu... 查看详情
bzoj3365:[usaco2004feb]distancestatistics路程统计容斥原理+点分治(代码片段)
统计在一个root下的两个子树，每个子树都和前面的运算一下再加进去对于这种需要排序的运算很麻烦，所以考虑先不去同子树内点对的算出合法点对个数，然后减去每一棵子树内的合法点对（它们实际上是不合法的，相当于一... 查看详情
bzoj4410:[usaco2016feb]fencein(代码片段)
...栏杆使得所有小矩形连通。如下图。------>用最小生成树的想法，贪心选最小的来割。 查看详情
[bzoj2591][usaco2012feb]nearbycows
2591:[Usaco2012Feb]NearbyCowsTimeLimit:4Sec MemoryLimit:128MBSubmit:149 Solved:89[Submit][Status][Discuss]Description FarmerJohnhasnoticedthathiscowsoftenmovebetweennearbyfi 查看详情
bzoj3942:[usaco2015feb]censoring
3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec MemoryLimit: 128MBSubmit: 404 Solved: 221[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiont 查看详情
bzoj3940[usaco2015feb]censoring
DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmaterialtoreadwhilewaitingaroundinthebarnduringmilkingsessions.Unfortunately,thelatestissuecontain 查看详情
bzoj1651:[usaco2006feb]stallreservations专用牛棚
二次联通门: BZOJ1651:[Usaco2006Feb]StallReservations专用牛棚 权限题放题面DescriptionOhthosepickyN(1<=N<=50,000)cows!TheyaresopickythateachonewillonlybemilkedoversomeprecisetimeintervalA.. 查看详情
[bzoj]1631:[usaco2007feb]cowparty
1631:[Usaco2007Feb]CowPartyTimeLimit:5Sec MemoryLimit:64MBSubmit:866 Solved:624[Submit][Status][Discuss]Description 农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X 查看详情
bzoj4412[usaco2016feb]circularbarn
先看成一条链for一遍找位置在for一遍算答案#include<algorithm>#include<iostream>#include<cstring>#include<string>#include<cstdio>#include<cmath>usingnamespacestd;typedeflonglongLL;#def 查看详情
[bzoj]1651:[usaco2006feb]stallreservations专用牛棚
1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit:10Sec MemoryLimit:64MBSubmit:987 Solved:566[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N<=50,000)cows!Theyaresopi 查看详情