[BZOJ1509][NOI2003]逃学的小孩（树形dp||dfs）

题目描述

传送门

题解

很显然是一道需要求直径的题呀，因为在最坏情况下一定会走一遍直径。dfs或者树形dp（需要把直径记录下来，dp我没有写过，没有负边权用dfs比较方便）。 找出来了直径之后，枚举直径上的每一个点，求出这些点不经过直径上任意一点能到达树上最远的那个点，这个点就是有可能的点C，然后更新答案就可以了。 这题确实是比较简单的，不过zz的我刚开始认为这三个点都在直径上，真是被自己蠢哭了T_T

代码

#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define N 200005 #define LL long long int n,m,x,y,l,r,root; LL z,Max,ans; int tot,point[N],nxt[N*2],v[N*2]; LL c[N*2]; int father[N],chain[N]; LL dis[N],ddis[N]; bool vis[N]; void addedge(int x,int y,LL z) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; c[tot]=z; } void dfs(int x,int fa) { father[x]=fa; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa) { dis[v[i]]=dis[x]+c[i]; dfs(v[i],x); } if (dis[x]>dis[root]) root=x; } void Chain() { int x=r; while (x!=father[l]) { vis[x]=true; chain[++chain[0]]=x; x=father[x]; } } void ddfs(int x,int fa) { vis[x]=true; for (int i=point[x];i;i=nxt[i]) if (v[i]!=fa&&!vis[v[i]]) { ddis[v[i]]=ddis[x]+c[i]; ddfs(v[i],x); } Max=max(Max,ddis[x]); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<n;++i) { scanf("%d%d%lld",&x,&y,&z); addedge(x,y,z); } dfs(1,0),l=root; memset(dis,0,sizeof(dis)),dfs(root,0),r=root; Chain(); for (int i=1;i<=chain[0];++i) { Max=0,ddfs(chain[i],0); LL now=dis[r]+min(dis[chain[i]],dis[r]-dis[chain[i]])+Max; ans=max(ans,now); } printf("%lld\n",ans); }