牛客练习赛40 C-小A与欧拉路

求图中最短的欧拉路。
题解：因为是一棵树，因此当从某一个节点遍历其子树的时候，如果还没有遍历完整个树，一定还需要再回到这个节点再去遍历其它子树，因此除了从起点到终点之间的路，其它路都被走了两次，而我们要求总的路程最短，那么我们就让从起点到终点的路最长即可，也就是树的直径。所以答案就是所有边权的两倍再减去树的直径

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long LL;

const int maxn=;

int n;

struct Edge

{

    int from,to;

    LL val;

};

vector<Edge>edge[maxn];

LL dp[maxn][];

void dfs(int u,int fa)

{

    dp[u][]=;dp[u][]=;

    int len=edge[u].size();

    for(int i=;i<len;i++)

    {

        int v=edge[u][i].to;

        LL w=edge[u][i].val;

        if(v==fa)

            continue;

        dfs(v,u);

        if(dp[v][]+w>dp[u][])//如果以u为根节点的最长链可以被它的儿子v更新

        {

            dp[u][]=dp[u][];//最长链变次长链

            dp[u][]=dp[v][]+w;//最长链被更新

        }

        else if (dp[v][]+w>dp[u][])//如果不能更新最长链但是却可以更新次长链

            dp[u][]=dp[v][]+w;

    }

}

int main()

{

    scanf("%d",&n);

    LL ans=;

    int f,t;LL v;

    Edge temp;

    for(int i=;i<n;i++)

    {

        scanf("%d %d %lld",&f,&t,&temp.val);

        temp.from=f;temp.to=t;

        edge[f].push_back(temp);

        temp.from=t;temp.to=f;

        edge[t].push_back(temp);

        ans+=(temp.val*);

    }

    dfs(,);

    LL maxx=;

    for(int i=;i<=n;i++)

        maxx=max(maxx,dp[i][]+dp[i][]);

    printf("%lld\n",ans-maxx);

    return ;

}

网看到了一个bfs 求树的直径的解法：贴一下

#include <iostream>

#include <cstring>

#include <queue>

using namespace std;

typedef long long ll;

const int MAX = 1e6+;

struct hh{

    int u,v,w;

    int nt;

}a[MAX];

int dis[MAX],head[MAX];

bool vis[MAX];

int n,tot,point,len;

ll ans;//注意要用long long

void add(int u,int v,int w){

    a[tot].v=v;

    a[tot].u=u;

    a[tot].w=w;

    a[tot].nt=head[u];

    head[u]=tot++;

}

void bfs(int s){//找树的直径模板

    memset(vis,false,sizeof(vis));//第二次要初始化，第一次一块带上了，嘻嘻~~不超时

    memset(dis,,sizeof(dis));//第二次要初始化，第一次一块带上了，嘻嘻~~不超时

    queue<int> q;

    q.push(s);

    vis[s]=;

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for (int i = head[x]; ~i; i = a[i].nt){

            int y=a[i].v;

            if(!vis[y]){

                dis[y]=dis[x]+a[i].w;

                if(len<dis[y]){

                    len=dis[y];

                    point=y;

                }

                vis[y]=true;

                q.push(y);

            }

        }

    }

}

int main(){

    cin >> n;

    memset(head,-,sizeof(head));

    for (int i = ; i < n-;i++){

        int u,v,w;

        cin >> u >> v >> w;

        add(u,v,w);//无向边，为双向的

        add(v,u,w);

        ans+=w<<;//树的权值*2

    }

    len=;

    bfs();//找到最远点

    len=;//len为树的直径~~，记住要初始化！

    bfs(point);//找直径，必须跑两边，记住！！！

    cout << ans-len << endl;

    return ;

}