大臣的旅费:
把子点和权值全连在父点上 然后以父点为最开始的遍历起点
然后dfs中常规遍历图方法:for循环遍历和这个父节点相连的所有边
if(这个节点没有遍历过) 就dfs这个节点 然后这个dfs的副作用是将距离加到当前遍历的节点u上
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
int n;
const int N=1e5+10;
bool st[N];
int dist[N];
vector<PII> h[N];
void dfs(int u,int distance)
{
st[u]=true;
dist[u]=distance;
for(auto tmp:h[u])
{
if(!st[tmp.x])
{
dfs(tmp.x,distance+tmp.y);
}
}
}
int main()
{
cin>>n;
int a,b,c;
for(int i=0;i<n-1;i++)
{
scanf("%d%d%d",&a,&b,&c);
h[a].push_back({b,c});
h[b].push_back({a,c});
}
dfs(1,0);
int maxn=0;
int tmp;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxn) maxn=dist[i],tmp=i;
}
memset(st,0,sizeof st);
memset(dist,0,sizeof dist);
dfs(tmp,0);
maxn=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxn) maxn=dist[i];
}
cout<<(long long)(1+maxn)*maxn/2+(long long)10*maxn;//这里记得不要把10*maxn放到(1+maxn)括号里面了(/捂脸)
return 0;
}
这是y总写法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct tree
{
int id,val;
};
const int N=100010;
int n;
vector<tree> h[N];
int dist[N];
void dfs(int u,int father,int distance)
{
dist[u]=distance;
for(auto tmp:h[u])
{
if(tmp.id!=father)//孙子不等于爷爷 或者因为双向边而导致的死循环(要是有环可能不太严谨 因为可能与father重合也可能和与之前遍历过的重合)
{
dfs(tmp.id,u,distance+tmp.val);
}
}
}
int main()
{
cin>>n;
int a,b,c;
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&a,&b,&c);
h[a].push_back({b,c});
h[b].push_back({a,c});
}
dfs(1,-1,0);
int temp=1;
for(int i=1;i<=n;i++)
{
if(dist[i]>dist[temp]) temp=i;//这里也是一步优化
}
// cout<<temp<<endl;
dfs(temp,-1,0);
int maxnum=0;
for(int i=1;i<=n;i++)
{
if(dist[i]>maxnum) maxnum=dist[i];
}
// cout<<maxnum<<endl;
printf("%lld",maxnum*10+maxnum*(maxnum+1ll)/2);
return 0;
}