写这个是因为觉得不能颓废了,基础不行就得补
没啥好说的,看oiwiki
!!!重点是一定要区分无向和有向
发现一个很良心的博客blog。
这模板题也是他出的
#include<bits/stdc++.h> using namespace std; #define ll long long #define LLF LLONG_MAX const int N=1e6; struct sss{ int v,nxt; ll val; }T[N<<1]; int head[N]; int tot; ll ans=-LLF; ll f[N]; void add(int u,int v,ll w) { T[++tot].v=v; T[tot].val=w; T[tot].nxt=head[u]; head[u]=tot; } void dfs(int u,int fa) { f[u]=0; for(int i=head[u];i;i=T[i].nxt) { int v=T[i].v; if(v==fa)continue; dfs(v,u); ans=max(ans,f[u]+f[v]+T[i].val); f[u]=max(f[u],f[v]+T[i].val); } } int main() { int n; scanf("%d",&n); int u,v; ll w; for(int i=1;i<n;i++) { scanf("%d%d%lld",&u,&v,&w); add(u,v,w); add(v,u,w); } dfs(1,1); printf("%lld",ans); return 0; }