国外比较好的建筑设计网站,做网站公司费用,北京做家政网站有哪些平台,手机网站菜单设计模板求一棵树的直径#xff0c;所谓直径就是树上距离最远的两个点#xff01; 树形动归#xff0c;每个点的为根的子树的最长向下链和次长链的和#xff01; 当然也可以二次深搜#xff01; ————————————————————————————————————————…求一棵树的直径所谓直径就是树上距离最远的两个点 树形动归每个点的为根的子树的最长向下链和次长链的和 当然也可以二次深搜 ———————————————————————————————————————————————————— 1 #includecstdio2 #includecstring3 #includealgorithm4 #includeiostream5 using namespace std;6 const int maxn10010;7 struct edge8 {9 int u,v,w,next;
10 }e[maxn1];
11 int head[maxn],js;
12 long long ans;
13 long long ml[maxn],sl[maxn];
14 void addage(int u,int v,int w)
15 {
16 e[js].uu;e[js].vv;e[js].ww;
17 e[js].nexthead[u];head[u]js;
18 }
19 void dfs(int u,int fa)
20 {
21 for(int ihead[u];i;ie[i].next)
22 {
23 int ve[i].v;
24 if(v!fa)
25 {
26 dfs(v,u);
27 if(ml[v]e[i].wml[u])
28 {
29 sl[u]ml[u];
30 ml[u]ml[v]e[i].w;
31 }
32 }
33 else if(ml[v]e[i].wsl[u])
34 sl[u]ml[v]e[i].w;
35 }
36 if(ml[u]sl[u]ans)ansml[u]sl[u];
37 }
38 int main()
39 {
40 int u,v,w;
41 while(scanf(%d%d%d,u,v,w)3)
42 {
43 addage(u,v,w);
44 addage(v,u,w);
45 }
46 dfs(1,0);
47 coutans;
48 return 0;
49 } View Code 转载于:https://www.cnblogs.com/gryzy/p/9842094.html
