[Codeforces 1016F]Road Projects

Description

Topic library link

Give you a tree\(n\) Tree of nodes\(1\) reach\(n\) The cost is\(1\) reach\(n\) The length of the shortest path between nodes. Now give it to you\(m\) The group asks you to add an edge weight.\(w\) The maximum value of the cost is not the same as the original graph. Questioning is independent of each other.

\(1\leq n,m\leq 3\times 10^5\)

Solution

Spicy chicken, Lao Yu destroys my youth.

hold\(1\) to\(n\) When the path is extracted, it is obvious that the graph becomes a chain plus some subtrees. Greedy thinking is to find such a group of points to meet.

1. Its subtree comes from two different points on the chain.
2. It must be the deepest point in the tree.

Then we can traverse the chain to find the maximum value that satisfies all the above conditions. Last\(O(1)\) Answer questions.

Attention is paid to special judgement.\(1\) or\(n\) The situation of nodes outside.

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 300000+5;

struct tt {int to, next, cost; } edge[N<<1];
int path[N], top;
int n, m, u, v, c, vis[N], sz[N], flag, f, szf;
ll dist[N], maxn = -1, ans, dis[N];

bool dfs(int u, int fa) {
    sz[u] = 1;
    for (int v, i = path[u]; i; i = edge[i].next)
        if ((v = edge[i].to) != fa) {
            dis[v] = dis[u]+edge[i].cost;
            if (dfs(v, u)) vis[u] = 1;
            else dist[u] = max(dist[u], dist[v]+edge[i].cost), flag += (u == n), f += (u == 1);
            sz[u] += sz[v];
        }
    return vis[u] |= (u == n);
}
void dfs2(int u, int fa) {
    for (int v, i = path[u]; i; i = edge[i].next)
        if ((v = edge[i].to) != fa && vis[v]) {
            if (u == 1) szf = sz[u]-sz[v];
            if (dist[fa] > 0) maxn = max(maxn, dist[fa]+dis[fa]);
            if (dist[u] > 0) maxn = max(maxn, dis[fa]);
            if (maxn != -1 && u != 1) ans = max(ans, maxn+dist[u]+dis[n]-dis[u]);
            if (dist[fa] == 0 && fa != 0) maxn = max(maxn, dis[fa]);
            dfs2(v, u);
        }
    if (u == n) {
        if (dist[fa] > 0) maxn = max(maxn, dist[fa]+dis[fa]);
        if (dist[u] > 0) maxn = max(maxn, dis[fa]);
        if (maxn != -1) ans = max(ans, maxn+dist[u]);   
    }
}
void add(int u, int v, int c) {edge[++top] = (tt){v, path[u], c}; path[u] = top; }
void work() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &c);
        add(u, v, c), add(v, u, c);
    }
    dfs(1, 0); dfs2(1, 0);
    while (m--) {
        scanf("%d", &c);
        if (flag > 1 || sz[n] >= 3) printf("%I64d\n", dis[n]);
        else if (f > 1 || szf >= 3) printf("%I64d\n", dis[n]);
        else printf("%I64d\n", min(c+ans, dis[n])); 
    }
}
int main() {work(); return 0; }