蓝桥集训之大臣的旅费

本文主要是介绍蓝桥集训之大臣的旅费，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蓝桥集训之大臣的旅费

• 核心思想：dfs求树的直径

  1. 从原点开始 找距离其最远的点 然后再找一次最远点 之间距离为直径
  2. 2次dfs即可求出最长距离

•   #include<bits/stdc++.h>using namespace std;const int N =1e6+10; int n ;int cnt[N] , e[N] , ne[N] , h[N] , idx ;int maxu , maxd ;void add(int a , int b , int c ){e[idx] = b , cnt[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ;}void dfs(int u,int fa,int d)  //fa为父亲节点 用st数组也可以 目的是不往回走{for(int i=h[u];i!=-1;i=ne[i]){int j = e[i];int k = cnt[i];if(j == fa) continue;  //不往回走if(maxd < d + k){maxd = d+k;maxu = j;}dfs(j,u,d+k);  //往下搜}}int main(){cin>>n;int k = n-1;memset(h,-1,sizeof h);while(k--){int a,b,d;scanf("%d%d%d",&a,&b,&d);add(a,b,d),add(b,a,d);}dfs(1,-1,0);dfs(maxu,-1,0);//推导公式 会爆int 用1ll 把1转化为longlong 结果就是longlong了printf("%lld\n", maxd * 10 + maxd * (maxd + 1ll) / 2);return 0;}
  

这篇关于蓝桥集训之大臣的旅费的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---