小A与欧拉路

小A与欧拉路

https://ac.nowcoder.com/acm/problem/22618

小A与欧拉路

分析

  • 欧拉路:

    该路径经过图的每一条边且仅经过一次。如果路径起点和终点相同,则称“欧拉回路”。具有欧拉回路的图称“欧拉图”。


  • 图片说明
    因为要求最短,那么path(x,y)最长即可。就是一个树的直径的模板

代码

/*树的直径*/
#include<bits/stdc++.h>

#define R register
#define ll long long
#define inf INT_MAX

using namespace std;

const int N=2e5+10;

int n,tot,ans,sum;
int h[N],nex[N<<1],ver[N<<1],pri[N];
int dis[N],f[N],g[N];

inline void add(int x,int y,int z)
{
    nex[tot]=h[x];
    ver[tot]=y;
    pri[tot]=z;
    h[x]=tot++;
}

inline void dfs(int u,int v)
{
    f[u]=g[u]=0;
    for (int i=h[u];~i;i=nex[i])
    {
        int j=ver[i];
        if(j==v) continue;

        dfs(j,u);

        if(f[j]+pri[i]>f[u])
        {
            g[u]=f[u];
            f[u]=f[j]+pri[i];
        }
        else g[u]=max(g[u],f[j]+pri[i]);
    }
    ans=max(ans,f[u]+g[u]);
}

int main()
{
    memset(h,-1,sizeof(h));
    scanf("%d",&n);
    for (int i=1;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);sum+=z;
    }

    dfs(1,0);

    printf("%lld\n",2ll*sum-(ll)ans);

    return 0;
}
每日一题 文章被收录于专栏

每天的题,为了牛币

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
面试尴尬现场
点赞 评论 收藏
分享
哈哈哈哈哈哈哈哈哈哈这个世界太美好了
凉风落木楚山秋:毕业出路老师不管,你盖个章他好交差就完事了,等你盖完毕业了就不关他事情了
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-04 14:23
steelhead:你回的有问题,让人感觉你就是来学习的
点赞 评论 收藏
分享
评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务