C++11(clang++ 3.9) 解法, 执行用时: 80ms, 内存消耗: 11816K, 提交时间: 2020-08-09 11:28:01

struct edge {
    int v,w;
};
typedef long long ll;
vector<edge> g[100005];
ll dis[100005];
void dfs(int u,int fa) {
    for(edge e:g[u]) {
        int v=e.v;
        if(v==fa) continue;
        dis[v]=dis[u]+e.w;
        dfs(v,u);
    }
}
class Solution {
public:
    /**
     * 最短距离
     * @param n int整型
     * @param Edge Point类vector
     * @param val int整型vector
     * @return long长整型
     */
    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        ll sum=0;
        for(int i=0;i<n-1;++i) {
            int u=Edge[i].x,v=Edge[i].y,w=val[i];
            g[u].push_back({v,w});
            g[v].push_back({u,w});
            sum+=w;
        }
        dfs(1,0);
        int rt=0;
        for(int i=1;i<=n;++i) if(dis[i]>dis[rt]) rt=i;
        dis[rt]=0;
        dfs(rt,0);
        ll d=0;
        for(int i=1;i<=n;++i) d=max(d,dis[i]);
        return 2*sum-d;
    }
};

Go(1.14.4) 解法, 执行用时: 88ms, 内存消耗: 16560K, 提交时间: 2020-08-01 22:03:24

package main

import . "nc_tools"

// github.com/EndlessCheng/codeforces-go
func solve(n int, edges []*Point, a []int) int64 {
	s := 0
	type neighbor struct{ to, wt int }
	g := make([][]neighbor, n+1)
	for i, e := range edges {
		v, w, wt := e.X, e.Y, a[i]
		s += wt
		g[v] = append(g[v], neighbor{w, wt})
		g[w] = append(g[w], neighbor{v, wt})
	}
	s <<= 1

	maxD, u := -1, 0
	var f func(v, fa, d int)
	f = func(v, fa, d int) {
		if d > maxD {
			maxD, u = d, v
		}
		for _, e := range g[v] {
			if e.to != fa {
				f(e.to, v, d+e.wt)
			}
		}
	}
	f(1, 0, 0)
	maxD = -1
	f(u, 0, 0)
	return int64(s - maxD)
}