解题思路:求树的直径,在使用等差数列的前n项和得出答案.
因为全为正数所以可以跑两边最长路就可以求出,此处给出树上dp
参考代码:
#include<bits/stdc++.h> using namespace std; struct node { int to; int w; int next; }mp[1000005]; int head[500005]; int cnt=0; void add(int a,int b,int c) { mp[++cnt].next=head[a]; mp[cnt].to=b; mp[cnt].w=c; head[a]=cnt; } int dp[500005]; int money=0; void dfs(int u,int fa) { for(int i=head[u];i;i=mp[i].next) { int v; v=mp[i].to; if(v==fa)continue; dfs(v,u); money=max(money,dp[u]+dp[v]+mp[i].w); dp[u]=max(dp[u],dp[v]+mp[i].w); } } int main() { int n; cin>>n; for(int i=1;i<n;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); } dfs(1,0); //cout<<money; printf("%lld",(long long)(10*money+money*(money+1)/2)); }
0.0分
0 人评分
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:2545 |
C语言程序设计教程(第三版)课后习题6.2 (C++代码)浏览:957 |
C语言训练-求PI* (C语言代码)浏览:897 |
C二级辅导-统计字符 (C语言代码)浏览:541 |
高精度加法 (C++代码)(大数加法)浏览:934 |
C语言训练-数字母 (C语言代码)浏览:649 |
IP判断 (C语言代码)浏览:764 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:557 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:462 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:550 |