关键词：
Description
给你一个图,两个点至多有一条路径,求最长的一条路径. (n leqslant 4 imes 10^4)
Sol
DFS?DP?
这就是一棵树,方向什么的都没用...
然后记录一下到这个点的最大值和次大值更新答案即可.
Code
/**************************************************************
Problem: 3363
User: BeiYu
Language: C++
Result: Accepted
Time:116 ms
Memory:5572 kb
****************************************************************/
#include<cstdio>
#include<vector>
#include<utility>
#include<iostream>
using namespace std;
#define mpr make_pair
typedef pair< int,int > pr;
const int N = 40005;
int n,m,ans;
vector<pr> g[N];
int mx1[N],mx2[N],b[N];
inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘ || ch<‘0‘) ch=getchar();
while(ch>=‘0‘ && ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; }
void DFS(int u,int fa){
b[u]=1;
for(int i=0,v,d;i<g[u].size();i++) if((v=g[u][i].first)!=fa){
DFS(v,u),d=g[u][i].second;
if(mx1[v]+d>mx1[u]) mx2[u]=mx1[u],mx1[u]=mx1[v]+d;
else if(mx1[v]+d>mx2[u]) mx2[u]=mx1[v]+d;
}ans=max(ans,mx1[u]+mx2[u]);
}
int main(){
n=in(),m=in();
for(int i=1,u,v,w;i<=m;i++){
u=in(),v=in(),w=in();
g[u].push_back(mpr(v,w)),g[v].push_back(mpr(u,w));
}
for(int i=1;i<=n;i++) if(!b[i]) DFS(i,-1);
cout<<ans<<endl;
return 0;
}
bzoj3362/3363/3364/3365[usaco2004feb]树上问题杂烩并查集/树形dp/lca/树的点分治
题目描述农夫约翰有N(2≤N≤40000)个农场，标号1到N,M(2≤M≤40000)条的不同的垂直或水平的道路连结着农场，道路的长度不超过1000.这些农场的分布就像下面的地图一样，图中农场用F1..F7表示, 每个农场最多能在东西南北四个方... 查看详情
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下的两个子树，每个子树都和前面的运算一下再加进去对于这种需要排序的运算很麻烦，所以考虑先不去同子树内点对的算出合法点对个数，然后减去每一棵子树内的合法点对（它们实际上是不合法的，相当于一... 查看详情
[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 查看详情
[bzoj1651][usaco2006feb]stallreservations专用牛棚
1651:[Usaco2006Feb]StallReservations专用牛棚TimeLimit:10Sec MemoryLimit:64MBSubmit:990 Solved:568[Submit][Status][Discuss]DescriptionOhthosepickyN(1<=N<=50,000)cows!Theyaresopi 查看详情
[bzoj1652][usaco06feb]treatsforthecows题解（区间dp）(代码片段)
[BZOJ1652][USACO06FEB]TreatsfortheCowsDescriptionFJhaspurchasedN(1<=N<=2000)yummytreatsforthecowswhogetmoneyforgivingvastamountsofmilk.FJsellsonetreatperdayandwantstomaximizethemoneyhereceivesov 查看详情