abc222 F – Expensive Expense

题意：

给定一棵树，边权为路费，点权为观光费。从 \(u\) 去 \(v\) 旅游的费用定义为路费加上 \(v\) 点的观光费

求从每个点出发到其它点旅游的最大费用

\(n\le 2e5\)

思路：

一眼换根dp，过了：https://atcoder.jp/contests/abc222/submissions/38238369

然而官方题解还有个妙妙直径做法，记录一下：

为原图 \(G\) 的每个点 \(u\) 加一个儿子 \(son\)，\(u-son\) 边的权为原来 \(u\) 的点权。这样得到只有边权没有点权的新图 \(G'\)

找 \(G'\) 的直径 \(l,r\)，根据直径的性质，答案是走到 \(l\) 或 \(r\) 的新加儿子处。注意特判一下，不能走到自己的新加儿子上

const int N = 4e5 + 5;
int n; vector<pair<int, int> > G[N];
ll f[N], g[N];
int bfs(int S, ll d[N]) {
    int p = S; //返回最远点
    queue<int> q; q.push(S);
    memset(d, -1, sizeof f); d[S] = 0;
    while(q.size()) {
        int u = q.front(); q.pop();
        if(d[u] > d[p]) p = u;
        for(auto [v, w] : G[u]) if(d[v] == -1)
            d[v] = d[u] + w, q.push(v);
    }
    return p;
}
void sol() {
    cin >> n;
    for(int i = 1; i < n; i++) {
        int x, y, z; cin >> x >> y >> z;
        G[x].push_back({y, z}), G[y].push_back({x, z});
    }
    for(int i = 1; i <= n; i++) {
        int d; cin >> d;
        G[i].push_back({i + n, d}), G[i + n].push_back({i, d});
    }
    
    int l = bfs(1, g), r = bfs(l, f);
    bfs(r, g);
    for(int i = 1; i <= n; i++) {
        if(i + n == l) cout << g[i] << '\n'; //别走到自己儿子上
        else if(i + n == r) cout << f[i] << '\n';
        else cout << max(f[i], g[i]) << '\n';
    }
}

官方题解是 dijkstra 在 \(G\) 上找最短路（话说直接 dfs/bfs 不就好了吗），得到最短路数组

然后用最短路数组 + 点权找直径的端点

详见 https://atcoder.jp/contests/abc222/editorial/2763