星空中有n颗星星，有n-1对星星间被人为地连上了线，每条连线有各自的长度。所有星星被连成了一个整体。现在，你要在星系中找到一个最大的十字形星座。即，你要找到两条星星构成的路径，使得它们恰好有一颗公共星（这颗公共星不能是某条路径的端点），且两条路径的长度和最大。
左图红线表示了一个合法的十字形星座，而右图的星座并不合法。
输入
第一行一个数n，表示星星的数量。
接下来n行，每行3个数x,y,z，表示第x颗星星和第y颗星星间有一条连线，它的长度是z。
输出
一行，包含一个整数，表示最大的路径长度和。若答案不存在，输出-1。
样例输入
10
3 8 6
9 3 5
1 9 2
4 8 6
2 3 3
10 4 8
5 9 5
7 2 3
6 9 1
样例输出
33
提示
20%的数据n<=1000
50%的数据n<=10,000
100%的数据n<=100,000，0<=z<=1000
这道题讲道理暴力应该有50分，但是打炸了~~
这里我们用一个f和g数组，任选一个树根，dfs树上DP，f[i][0][1][2][3]分别表示从i开始，向下走到某个叶子为止最长、第二长、第三长、第四长的路径长度。从叶子向树根的顺序DP。
#include<iostream> #include<cstdio> #include<algorithm> #define maxn 100005 using namespace std; int head[maxn],next[maxn*2],ans=0,n,dis[maxn],num=0,val[maxn*2],to[maxn*2],s[maxn][5],b[maxn][5],g[maxn]; void make_way(int u,int v,int c) { to[++num]=v; next[num]=head[u]; val[num]=c; head[u]=num; } int dfs(int u,int fa) { for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { dis[to[edge]]=dis[u]+val[edge]; dfs(to[edge],u); int p=s[to[edge]][1]+val[edge]; if(p>s[u][1]){ s[u][4]=s[u][3]; b[u][4]=b[u][3]; s[u][3]=s[u][2]; b[u][3]=b[u][2]; s[u][2]=s[u][1]; b[u][2]=b[u][1]; s[u][1]=p; b[u][1]=to[edge]; }else if(p>s[u][2]) { s[u][4]=s[u][3]; b[u][4]=b[u][3]; s[u][3]=s[u][2]; b[u][3]=b[u][2]; s[u][2]=p; b[u][2]=to[edge]; }else if(p>s[u][3]) { s[u][4]=s[u][3]; b[u][4]=b[u][3]; s[u][3]=p; b[u][3]=to[edge]; }else if(p>s[u][4]) s[u][4]=p,b[u][4]=p; } return dis[u]; } void dp(int u,int fa) { for(int edge=head[u];edge;edge=next[edge]) if(to[edge]!=fa) { if(to[edge]==b[u][1]) g[to[edge]]=max(s[u][2],g[u])+val[edge];else g[to[edge]]=max(s[u][1],g[u])+val[edge]; dp(to[edge],u); } if(s[u][4]) ans=max(ans,s[u][4]+s[u][1]+s[u][2]+s[u][3]); if(s[u][3]) ans=max(ans,s[u][1]+s[u][2]+s[u][3]+g[u]); } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,c; scanf("%d %d %d",&u,&v,&c); make_way(u,v,c); make_way(v,u,c); } dfs(1,0); dp(1,0); cout<<ans<<endl; }