2021 Jiangxi Provincial Collegiate Programming Contest I Homework

题目描述

http://codeforces.com/gym/103366/problem/I

简要题意：给定一个棵有 $n$ 个点的无根树，现在有 $m$ 次操作，操作有三种：修改某一个点的权值；修改某一条边的权值；查询每个点完成作业的时间。在这颗树上，每个点有一个人，每个人单独完成作业所需的时间为 $a_i$，每个人除了单独完成作业，还可以去别人那里请教，如果 $i$ 要向 $j$ 请教，则必须等 $j$ 完成作业之后，才能出发到 $j$ 所在的位置请教，然后返回自己所在的位置，注意如果 $i$ 向别人请教作业，那么只有当他回到自己位置后，才算他完成作业，另外需要注意的是，$i$ 到 $j$ 请教并返回的总时间为 $i$ 到 $j$ 的最短路径的长度的一倍

$n,m\le 10^5$，最多只有 $200$ 查询

Solution

注意到询问只有 $200$ 个，所以我们可以考虑每次查询时使用 $O(n)$ 或者时间复杂度更高的算法

现在我们考虑如何完成一次计算，注意到我们必须按照时间来更新，那么这本质上就是一个 $dijkstra$ 的过程，但是如果使用 $dijkstra$ 的时间复杂度是 $O(200n\log n)$ 的，不能通过此题

注意到我们的结构是一棵树而不是一张图，一个点只能由它的儿子或者父亲更新，那么我们直接 $up~and~down$ 一遍就好

#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

int n, m, a[maxn];

struct Edge {
    int to, next, w;
} e[maxn * 2]; int head[maxn], c1; 
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn], g[maxn];
void dfs(int u, int fa) {
    f[u] = a[u];
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w; if (v == fa) continue;
        dfs(v, u); f[u] = min(f[u], f[v] + w);
    } 
}

void Dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w; if (v == fa) continue;
        g[v] = min(f[v], g[u] + w);
        Dfs(v, u);
    }
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    a[x] = y; 
}

inline void solve_2() {
    int x, y; cin >> x >> y; --x;
    e[x * 2].w = e[x * 2 ^ 1].w = y;
}

inline void solve_3() {
    dfs(1, 0); g[1] = f[1]; Dfs(1, 0);
    int ans = 0; 
    for (int i = 1; i <= n; ++i) ans ^= g[i];
    cout << ans << "\n";
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int x, y, z; cin >> x >> y >> z;
        add_edge(x, y, z); add_edge(y, x, z);
    }
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        switch (opt) {
        case 1: solve_1(); break;
        case 2: solve_2(); break;
        case 3: solve_3(); break;
        }
    }
    return 0;
}