CCF-CSP认证考试 202309-5 阻击 48/60/72/100分题解

更多 CSP 认证考试题目题解可以前往：CSP-CCF 认证考试真题题解

原题链接： 202309-5 阻击

时间限制： 2.0s
内存限制： 512.0MB

问题描述

上回提到，西西艾弗岛下方有一个庞大的遗迹群，栖息着一种名为“阴阳龙”的神兽。然而隔壁的狄迪吉岛盯上了西西艾弗岛，决定发动一场战争，试图从遗迹群中掠夺有价值的宝物。由此，西西艾弗岛不得不陷入一场漫长的阻击战中，史称“阴阳龙阻击战”。

狄迪吉岛拥有胜过西西艾弗岛的科技实力和武装水平，西西艾弗岛很快发现形势不妙：全歼敌军似乎是不可能的，唯一的策略是凭借主场作战的优势和人海战术，尽可能给敌军带来损失，当敌军发现发动进攻的损失明显超过收益时，就会无趣而归。

具体而言，西西艾弗岛共有 $n$ 座城市，有 $n - 1$ 条道路连接这些城市，使得所有城市之间均可以通过道路互相到达。容易发现，任意两座城市之间都有唯一一条不经过重复城市的路径。

由于缺乏城市巷战的实力，西西艾弗岛决定将防御重心放在道路上。在每条道路上均派遣了一定的军队防守，当敌军经过时对其发动阻击。虽然由于实力的差距，并不能阻止敌军通过道路，但仍然可以对敌军造成一定的损失。

然而，敌军具有更强的科技，可以趁机对道路附近的遗迹进行探索，并掠夺其中的宝物——这也正是敌军发动战争的意义所在。如此，敌军通过一条道路时，“发掘宝物的收益” $w$ 和“受到阻击的损失” $b$ 两个值是独立的。

西西艾弗岛事先在狄迪吉岛中安插了一系列间谍，得到的情报消息如下：敌军将选择西西艾弗岛的两座城市作为进攻的“起点”和“终点”，并派遣军队在进攻起点城市登陆，沿两座城市间唯一的路径进攻至终点城市。同时，间谍还背负着另外一个重要的使命：影响敌军对于起点和终点城市的决策，使得敌军受到的总损失尽可能大，其中“总损失”定义为敌军经过的每条道路上的“受到阻击的损失”减去“发掘宝物的收益”之和，即 $\text{总损失} = \sum_{e \text{是路径上的每条边}}(b_e - w_e)$ 。

此外，遗迹中宝物的价值与所处的环境属性密切相关，而阴阳龙的“现身”会使得环境的阴阳属性发生变化，这会使得敌军通过现身位置处的某一条道路时“发掘宝物的收益” $w$ 发生变化。

这样的“阴阳龙现身”事件共会发生 $m$ 次，你的任务就是帮助间谍计算出在所有事件前及每次事件后，敌军对于起点和终点城市的决策应当怎样改变，以最大化敌军的总损失。

输入格式

从标准输入读入数据。

第 $1$ 行，两个非负整数 $n, m$ ，分别表示西西艾弗岛的城市数和“阴阳龙现身”事件数。

接下来 $n - 1$ 行，每行 $4$ 个非负整数 $u_i,v_i,w_i,b_i$ ，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$ ，敌军在这条道路上“发掘宝物的收益”为 $w_i$ ，“受到阻击的损失”为 $b_i$ 。

接下来 $m$ 行，每行 $2$ 个非负整数 $x_i,y_i$ ，表示一次“阴阳龙现身”事件，使得第 $x_i$ 条道路的“发掘宝物的收益”变为 $y_i$ 。

输出格式

输出到标准输出中。

输出 $m + 1$ 行，每行一个非负整数，分别表示在所有事件前及每次事件后，对敌军造成的最大总损失。

样例输入

样例输出

样例说明

在最初，由于敌人攻打每一条道路都会有正收益，因此间谍最好的策略就是将进攻起点和终点选为同一座城市，这样敌军的总损失为 $0$ 。

第 $1$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $3$ 和 $4$ ，这样敌军的总损失为 $3 - 2 = 1$ 。

第 $2$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $4$ 和 $5$ ，这样敌军的总损失为 $(3 - 2) + (5 - 3) = 3$ 。

第 $3$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $1$ 和 $5$ ，这样敌军的总损失为 $(4 - 1) + (1 - 2) + (5 - 3) = 4$ 。

评测用例规模与约定

对于所有测试数据保证： $2\leq n \leq 10^5, 0 \leq m \leq 10^5, 1 \leq u_i,v_i \leq n, 1 \leq x_i \leq n-1, 0 \leq w_i,b_i,y_i \leq 10^9$ 。

测试点编号	$\leq$	$\leq$	特殊性质
$1$	$20$	$20$	无
$2$	$300$	$300$	无
$\sim 4$	$3000$	$3000$	A
$\sim 6$	$3000$	$3000$	B
$\sim 9$	$3000$	$3000$	无
$10$	$10^5$	$0$	A
$11$	$10^5$	$0$	B
$12$	$10^5$	$0$	无
$\sim 15$	$10^5$	$10^5$	A
$\sim 18$	$10^5$	$10^5$	B
$\sim 21$	$10^5$	$10^5$	C
$\sim 25$	$10^5$	$10^5$	无

特殊性质 A： $u_i=i,v_i=i+1$ 。

特殊性质 B： $\leq w_i,y_i \leq 10^8 \leq b_i$ 。

特殊性质 C：保证任意两座城市均可在经过不超过 $100$ 条道路的前提下互相到达。

48 分题解（测试点 1~12）

对于给定的一棵树，可以在 $\mathcal{O}(n)$ 时间内通过树形 dp 求出最长路径。题目中相当于求 $m + 1$ 棵树的最长路径。

对于一棵给定的树，设 $dp_{u,0}$ 表示 $u$ 子树中的最长路径； $dp_{u,1}$ 表示从 $u$ 开始的最长链； $dp_{u,1}$ 表示从 $u$ 开始的次长链。

转移方程为：

$dp_{u,0}=\max\{0,dp_{v,0},dp_{u,1}+dp_{u,2}\}$ ；
$dp_{u,1}=\max\{0,f_{v,1}+w\}$ ；
$dp_{u,2}=\mathrm{secondmax}\{0,0,f_{v,1}+w\}$ （写两个 $0$ 是保证第二大的值非负）。

时间复杂度： $\mathcal{O}(nm)$ 。

48 分参考代码（运行超时，36.28MB）

/*
    Created by Pujx on 2024/3/16.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include ""
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
int n, m, t, k, q;

vector<int> graph[N];
struct edge { int u, v; i64 w, b; } e[N];
int tot;

i64 dp[N][3];
void dfs(int u, int fa) {
    dp[u][0] = dp[u][1] = dp[u][2] = 0;
    for (auto i : graph[u]) {
        int v = e[i].u ^ e[i].v ^ u;
        if (v == fa) continue;
        i64 w = e[i].b - e[i].w;
        dfs(v, u);
        if (dp[v][1] + w > dp[u][1]) dp[u][2] = dp[u][1], dp[u][1] = dp[v][1] + w;
        else if (dp[v][1] + w > dp[u][2]) dp[u][2] = dp[v][1] + w;
        dp[u][0] = max({dp[u][0], dp[v][0], dp[u][1] + dp[u][2]});
    }
}

void work() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        ++tot;
        cin >> e[tot].u >> e[tot].v >> e[tot].w >> e[tot].b;
        graph[e[tot].u].emplace_back(tot);
        graph[e[tot].v].emplace_back(tot);
    }

    dfs(1, -1);
    cout << dp[1][0] << endl;
    while (m--) {
        int x, y;
        cin >> x >> y;
        e[x].w = y;
        dfs(1, -1);
        cout << dp[1][0] << endl;
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

60 分题解（测试点 1~15）

测试点 $1\sim 12$ 与 $48$ 分题解中的一致，可以通过判断 $nm\leq 10^7$ 来进行区分。

测试点 $13\sim 15$ 给的是一条树链，如此该问题是一个经典的求数组的最大连续子数组的和。

使用可以单点修改的线段树来进行维护，对线段树的每个节点，记录下列信息：

l、r：该节点所代表的区间为 $[l, r]$ ；
sum：从 $l$ 到 $r$ 的和，即 $\sum\limits_{i=l}^r(b_i-e_i)$ ；
mx：从 $l$ 到 $r$ 的最大连续子数组的和，即 $\max\left\{\max\limits_{l\leq j\leq k\leq r}\left\{\sum\limits_{i=j}^k(b_i-e_i)\right\},0\right\}$ ；
pre：从 $l$ 开始的前缀和最大值，即 $\max\left\{\max\limits_{k=l}^r\left\{\sum\limits_{i=l}^k(b_i-e_i)\right\},0\right\}$ ；
suf：到 $r$ 结束的后缀和最大值，即 $\max\left\{\max\limits_{k=l}^r\left\{\sum\limits_{i=k}^r(b_i-e_i)\right\},0\right\}$ ；

pushup 时，父节点 s 与左儿子节点 ls、右儿子节点 rs 之间的关系为：

$sum_s=sum_{ls}+sum_{rs}$ ；
$mx_s=\max\{mx_{ls},mx_{rs},suf_{ls}+pre_{rs}\}$ ；
$pre_s=\max\{pre_{ls},sum_{ls}+pre_{rs},0\}$ ；
$suf_s=\max\{suf_{rs},suf_{ls}+sum_{rs},0\}$ 。

对于每次查询，只要输出线段树的根节点的 $m x$ 值即可。

时间复杂度：测试点 $1\sim 12$ ： $\mathcal{O}(nm)$ ；测试点 $13\sim 15$ ： $\mathcal{O}((n+m)\log n)$ 。

60 分参考代码（156ms，30.23MB）

/*
    Created by Pujx on 2024/3/16.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include ""
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
int n, m, t, k, q;

vector<int> graph[N];
struct edge { int u, v; i64 w, b; } e[N];
int tot;

i64 dp[N][3];
void dfs(int u, int fa) {
    dp[u][0] = dp[u][1] = dp[u][2] = 0;
    for (auto i : graph[u]) {
        int v = e[i].u ^ e[i].v ^ u;
        if (v == fa) continue;
        i64 w = e[i].b - e[i].w;
        dfs(v, u);
        if (dp[v][1] + w > dp[u][1]) dp[u][2] = dp[u][1], dp[u][1] = dp[v][1] + w;
        else if (dp[v][1] + w > dp[u][2]) dp[u][2] = dp[v][1] + w;
        dp[u][0] = max({dp[u][0], dp[v][0], dp[u][1] + dp[u][2]});
    }
}

template <typename T> struct SegmentTree {
    struct TreeNode { int l, r; T sum, mx, pre, suf; } tr[N << 2];
    void pushup(int s) {
        tr[s].sum = tr[ls].sum + tr[rs].sum;
        tr[s].mx = max({tr[ls].mx, tr[rs].mx, tr[ls].suf + tr[rs].pre, T()});
        tr[s].pre = max({tr[ls].pre, tr[ls].sum + tr[rs].pre, T()});
        tr[s].suf = max({tr[rs].suf, tr[rs].sum + tr[ls].suf, T()});
    }
    void build(int l, int r, int s = 1) {
        tr[s].l = l, tr[s].r = r;
        tr[s].sum = T(), tr[s].mx = numeric_limits<T>::min();
        tr[s].pre = tr[s].suf = numeric_limits<T>::min();
        if (l == r) {
            tr[s].sum = tr[s].mx = tr[s].pre = tr[s].suf = e[l].b - e[l].w;
            return;
        }
        int mid = l + r >> 1;
        if (l <= mid) build(l, mid, ls);
        if (mid < r) build(mid + 1, r, rs);
        pushup(s);
    }
    void update(int p, T val, int s = 1) {
        if (tr[s].l == tr[s].r) {
            tr[s].sum = tr[s].mx = tr[s].pre = tr[s].suf = val;
            return;
        }
        int mid = tr[s].l + tr[s].r >> 1;
        if (p <= mid) update(p, val, ls);
        else update(p, val, rs);
        pushup(s);
    }
    T query(int s = 1) {
        return tr[s].mx;
    }
};
SegmentTree<i64> T;

void work() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        ++tot;
        cin >> e[tot].u >> e[tot].v >> e[tot].w >> e[tot].b;
        graph[e[tot].u].emplace_back(tot);
        graph[e[tot].v].emplace_back(tot);
    }

    if (1ll * n * m <= 1e7) {
        // 测试点 1 ~ 12
        dfs(1, -1);
        cout << dp[1][0] << endl;
        while (m--) {
            int x, y;
            cin >> x >> y;
            e[x].w = y;
            dfs(1, -1);
            cout << dp[1][0] << endl;
        }
    }
    else {
        // 测试点 13 ~ 15
        T.build(1, n - 1);
        cout << T.query() << endl;
        while (m--) {
            int x, y;
            cin >> x >> y;
            e[x].w = y;
            T.update(x, e[x].b - e[x].w);
            cout << T.query() << endl;
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

72 分题解（测试点 1~15、19~21）

测试点 $13\sim 15$ 与 $60$ 分题解中的一致，可以通过判断 $u_i=i,v_i=i+1$ 来进行区分。

测试点 $19\sim 21$ 保证任意两座城市均可在经过不超过 $100$ 条道路的前提下互相到达，即树的深度不会超过 $100$ 。

回看 $48$ 分题解中对于每次询问的操作，会发现有大量的 $d p$ 值并不会更改，只有从修改边权的边的节点到根节点之间的 $d p$ 值会更改，但我们仍然会去计算整棵树的 $d p$ ，因此，这几个得分点可以通过优化解决这个问题来实现。

对于每个节点，我们开两个 set 来维护需要取 $\max$ 的内容，即 $dp_{u,0}$ 为 st0[u] 中的最大值， $dp_{u,1},dp_{u,2}$ 分别为 st12[u] 中的最大值和次大值。每次更新的时候，先将旧值从集合中删除（这里我是存储了旧值），再将新值放到集合中，最后在根据集合中的内容去更新 $d p$ 数组。由于树的高度不超过 $100$ ，因此对于单次的询问不会超过 $100$ 个点的更新。

由于测试点 $1\sim 12$ 的 $n, m$ 较小，故将其并在了这种情况中一起书写，当然也可以和 $48$ 分题解中的方法一致。

时间复杂度：测试点 $1\sim 12$ ： $\mathcal{O}(nm)$ ；测试点 $13\sim 15$ ： $\mathcal{O}((n+m)\log n)$ ；测试点 $19\sim 21$ ： $\mathcal{O}((n+100m)\log n)$ 。

72 分参考代码（运行超时，109.1MB）

/*
    Created by Pujx on 2024/3/16.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include ""
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
int n, m, t, k, q;

vector<int> graph[N];
struct edge { int u, v; i64 w, b; } e[N];
int tot;

int dep[N], fa[N];
i64 dp[N][3];
multiset<i64> st0[N], st12[N];
map<int, pair<i64, int>> inform0[N], inform12[N];
void dfs(int u, int f) {
    fa[u] = f;
    st0[u].insert(0), st12[u].insert(0), st12[u].insert(0);
    for (auto i : graph[u]) {
        int v = e[i].u ^ e[i].v ^ u;
        if (v == f) continue;
        i64 w = e[i].b - e[i].w;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        st0[u].insert(dp[v][0]);
        inform0[u][v] = {dp[v][0], i};
        st12[u].insert(max(0ll, dp[v][1] + w));
        inform12[u][v] = {max(0ll, dp[v][1] + w), i};
    }
    dp[u][2] = *++st12[u].rbegin();
    dp[u][1] = *st12[u].rbegin();
    dp[u][0] = max(*st0[u].rbegin(), dp[u][1] + dp[u][2]);
}

template <typename T> struct SegmentTree {
    struct TreeNode { int l, r; T sum, mx, pre, suf; } tr[N << 2];
    void pushup(int s) {
        tr[s].sum = tr[ls].sum + tr[rs].sum;
        tr[s].mx = max({tr[ls].mx, tr[rs].mx, tr[ls].suf + tr[rs].pre, T()});
        tr[s].pre = max({tr[ls].pre, tr[ls].sum + tr[rs].pre, T()});
        tr[s].suf = max({tr[rs].suf, tr[rs].sum + tr[ls].suf, T()});
    }
    void build(int l, int r, int s = 1) {
        tr[s].l = l, tr[s].r = r;
        tr[s].sum = T(), tr[s].mx = numeric_limits<T>::min();
        tr[s].pre = tr[s].suf = numeric_limits<T>::min();
        if (l == r) {
            tr[s].sum = tr[s].mx = tr[s].pre = tr[s].suf = e[l].b - e[l].w;
            return;
        }
        int mid = l + r >> 1;
        if (l <= mid) build(l, mid, ls);
        if (mid < r) build(mid + 1, r, rs);
        pushup(s);
    }
    void update(int p, T val, int s = 1) {
        if (tr[s].l == tr[s].r) {
            tr[s].sum = tr[s].mx = tr[s].pre = tr[s].suf = val;
            return;
        }
        int mid = tr[s].l + tr[s].r >> 1;
        if (p <= mid) update(p, val, ls);
        else update(p, val, rs);
        pushup(s);
    }
    T query(int s = 1) {
        return tr[s].mx;
    }
};
SegmentTree<i64> T;

void update(int u, int v) {
    while (~u) {
        auto& in0 = inform0[u][v];
        auto& in12 = inform12[u][v];
        st0[u].erase(st0[u].find(in0.ft));
        st12[u].erase(st12[u].find(in12.ft));

        int w = e[in0.se].b - e[in0.se].w;
        st0[u].insert(dp[v][0]);
        in0.ft = dp[v][0];
        st12[u].insert(max(0ll, dp[v][1] + w));
        in12.ft = max(0ll, dp[v][1] + w);

        dp[u][2] = *++st12[u].rbegin();
        dp[u][1] = *st12[u].rbegin();
        dp[u][0] = max(*st0[u].rbegin(), dp[u][1] + dp[u][2]);
        u = fa[u], v = fa[v];
    }
}

void work() {
    cin >> n >> m;
    bool isChain = true;
    for (int i = 1; i < n; i++) {
        ++tot;
        cin >> e[tot].u >> e[tot].v >> e[tot].w >> e[tot].b;
        isChain &= e[tot].u == i && e[tot].v == i + 1;
        graph[e[tot].u].emplace_back(tot);
        graph[e[tot].v].emplace_back(tot);
    }

    if (1ll * n * m <= 1e7 || !isChain) {
        // 测试点 1 ~ 12, 19 ~ 21
        dfs(1, -1);
        cout << dp[1][0] << endl;
        while (m--) {
            int x, y;
            cin >> x >> y;
            int u = e[x].u, v = e[x].v;
            if (dep[u] > dep[v]) swap(u, v);
            e[x].w = y;
            update(u, v);
            cout << dp[1][0] << endl;
        }
    }
    else {
        // 测试点 13 ~ 15
        T.build(1, n - 1);
        cout << T.query() << endl;
        while (m--) {
            int x, y;
            cin >> x >> y;
            e[x].w = y;
            T.update(x, e[x].b - e[x].w);
            cout << T.query() << endl;
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

100 分题解

可以说与前面基本没啥关系，看题签就知道了。

使用动态规划和树链剖分（重链剖分，记 $top_u$ 表示 $u$ 所在重链的顶部节点，记 $btn_u$ 表示 $u$ 所在重链的底部节点，下同），将给定的树转换为以 $1$ 为根的有根树：

$f_{u,0}$ 表示 $u$ 子树中，不经过 $u$ 的最长路径；
$f_{u,1}$ 表示 $u$ 子树中，经过 $u$ 的最长路径；
$f_{u,2}$ 表示仅考虑 $u$ 的重儿子分支，从 $u$ 开始的最长链；
$f_{u,3}$ 表示从 $u$ 开始的最长链；
$g_{u,0}$ 表示不考虑 $u$ 的重儿子分支，在 $u$ 子树中，不经过 $u$ 的最长路径；
$g_{u,1}$ 表示不考虑 $u$ 的重儿子分支，在 $u$ 子树中，经过 $u$ 的最长路径；
$g_{u,2}$ 表示不考虑 $u$ 的重儿子分支，从 $u$ 开始的最长链；
$g_{u,3}$ 表示不考虑 $u$ 的重儿子分支，从 $u$ 开始的次长链；
所有值都要和 $0$ 取 $\max$ ，即如果为最长的长度负时，不进行选择；
最终的答案为 $max\{f_{1,0},f_{1,1}\}$ 。

考虑动态规划的转移方程（存在 $u\to v$ 的有向边，边权为 $w$ ，且 $v$ 不是 $u$ 的重儿子； $son_u$ 表示 $u$ 的重儿子，下同）：

$f_{u,0}=\max\{f_{son_u,0},f_{son_u,1},g_{u,0}\}$ ；
$f_{u,1}=\max\{f_{u,2}+g_{u,2},g_{u,2}+g_{u,3}\}$ ；
$f_{u,2}=\max\{0,f_{son_u,3}+w\}$ ；
$f_{u,3}=\max\{f_{u,2},g_{u,2}\}$ ；
$g_{u,0}=\max\{f_{v,0},f_{v,1}\}$ ；
$g_{u,1}=g_{u,2}+g_{u,3}$ ；
$g_{u,2}=\max\{0,f_{v,2}+w,g_{v,2}+w\}$ ；
$g_{u,3}=\mathrm{secondmax}\{0,0,f_{v,2}+w,g_{v,2}+w\}$ （写两个 $0$ 是保证第二大的值非负）；
对于叶子结点，所有值均赋为 $0$ 。

考虑边权的更改对 $g$ 的影响：

对于一条重边（ $u\to son_u$ ）的边权更改，并不会影响到 $u$ 的 $g$ 值，但是会影响到 $fa_{top_u}$ （ $fa_u$ 表示 $u$ 的父节点）的值， $fa_{top_{fa_{top_u}}}$ 等递归往上一直到根节点，根据树链剖分的性质可以知道，影响的值不超过 $log_2n$ 个。
对于一条轻边（ $u\to v$ ）的边权更改，除了影响到上述重边的，还会影响到 $u$ 的 $g$ 值。
对于边权的修改，由于个数的数量级在 $log_2n$ ，可以暴力的去更新 $g$ 值。

余下要解决如何快速求出 $f$ 值：使用广义矩阵乘来进行维护。

对于矩阵 $\mathbf A=(a_{i,j})_{m\times n}$ ， $\mathbf B=(b_{i,j})_{n\times q}$ ，广义矩阵乘的结果 $\mathbf C=(c_{i,j})_{m\times q}$ 满足 $c_{i,j}=\max\limits_{k=1}^n(a_{i,k}+b_{k,j})$

这样根据转移方程，得出其矩阵转移形式： $\begin{pmatrix} 0 & 0 & -\infty & -\infty & g_{u,0} \\ -\infty & -\infty & -\infty & w+g_{u,2} & g_{u,2}+g_{u,3} \\ -\infty & -\infty & -\infty & w & 0 \\ -\infty & -\infty & -\infty & w & g_{u,2} \\ -\infty & -\infty & -\infty & -\infty & 0 \end{pmatrix} \begin{pmatrix} f_{son_u,0} \\ f_{son_u,1} \\ f_{son_u,2} \\ f_{son_u,3} \\ 0 \end{pmatrix} =\begin{pmatrix} f_{u,0} \\ f_{u,1} \\ f_{u,2} \\ f_{u,3} \\ 0 \end{pmatrix}$

使用线段树维护区间矩阵乘信息，并支持单点修改（按照 dfs 序进行存储，优先遍历重儿子，记 $u$ 的 dfs 序为 $dfn_u$ ），如果 $u$ 时叶子节点，矩阵的值为单位阵 $\mathbf E=\begin{pmatrix} 0 & -\infty & -\infty & -\infty &-\infty \\ -\infty & 0 & -\infty & -\infty & -\infty \\ -\infty & -\infty & 0 & -\infty & -\infty \\ -\infty & -\infty & -\infty & 0 & -\infty \\ -\infty & -\infty & -\infty & -\infty & 0 \end{pmatrix}$ 否则值为上述转移矩阵即可，询问 $u$ 点的 $f$ 值时，只需要询问从 $dfn_u$ 到 $dfn_{btn_u}$ 的矩阵乘积 $\mathbf X_{dfn_u},\cdots,\mathbf X_{dfn_{btn_u}}$ ，再去与 $btn_{u}$ 的 $f$ 值的矩阵进行乘积即可，即 $\begin{pmatrix} f_{u,0} \\ f_{u,1} \\ f_{u,2} \\ f_{u,3} \\ 0 \end{pmatrix} =\mathbf X_{dfn_u}\cdots\mathbf X_{dfn_{btn_u}}\begin{pmatrix} f_{btn_u,0} \\ f_{btn_u,1} \\ f_{btn_u,2} \\ f_{btn_u,3} \\ 0 \end{pmatrix}$ 其中，由于 $btn_u$ 是叶子结点， $f_{btn_u,0},f_{btn_u,1},f_{btn_u,2},f_{btn_u,3}$ 均为 $0$ 。

这样维护后，在更新 $u\to v$ 的边权时，先求出 $v$ 节点的 $f$ 值，然后再去更新 $u$ 的 $g$ 值，最后对线段树上的 $dfn_u$ 进行单点更新。

在重载矩阵乘法的时候不建议使用三重循环 $5^3$ 的做法（因为我被卡常了，可能是我写丑了），而是将其展开书写，预处理一些确定的值，再逐个计算其他值。

时间复杂度： $\mathcal{O}(n\log n+m\log^2n)$ 。

100 分参考代码（1.703s，269.2MB）

/*
    Created by Pujx on 2024/3/14.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include ""
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
int n, m, t, k, q;

struct GeneralizedMatrix {
    int m, n; // m 行 n 列的矩阵
    i64 v[5][5];
    bool isE = false;

    GeneralizedMatrix(): n(0), m(0) {}
    GeneralizedMatrix(int r, int c, i64 num = 0) : m(r), n(c) {
        for (int i = 0; i < r; i++)
            for (int j = 0; j < c; j++)
                v[i][j] = num;
    }
    GeneralizedMatrix(int n) : m(n), n(n) { // 单位矩阵的构造函数
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                v[i][j] = !(i == j) * (-INF);
        isE = true;
    }

    friend GeneralizedMatrix operator * (const GeneralizedMatrix& a, const GeneralizedMatrix& b) {
        assert(a.n == b.m);
        GeneralizedMatrix ans(a.m, b.n, -INF);
        ans.isE = a.isE && b.isE;
        if (a.isE) return b;
        else if (b.isE) return a;
        else if (b.n == 1) {
            ans[0][0] = max({b[0][0], b[1][0], a[0][3] + b[3][0], a[0][4]});
            ans[1][0] = max({a[1][3] + b[3][0], a[1][4]});
            ans[2][0] = max({a[2][3] + b[3][0], a[2][4]});
            ans[3][0] = max({a[3][3] + b[3][0], a[3][4]});
            ans[4][0] = 0;
        }
        else {
            ans[0][0] = ans[0][1] = ans[4][4] = 0;
            ans[0][3] = max({b[0][3], b[1][3], a[0][3] + b[3][3]});
            ans[0][4] = max({b[0][4], b[1][4], a[0][3] + b[3][4], a[0][4]});
            ans[1][3] = a[1][3] + b[3][3];
            ans[1][4] = max(a[1][3] + b[3][4], a[1][4]);
            ans[2][3] = a[2][3] + b[3][3];
            ans[2][4] = max(a[2][3] + b[3][4], a[2][4]);
            ans[3][3] = a[3][3] + b[3][3];
            ans[3][4] = max(a[3][3] + b[3][4], a[3][4]);
        }
        return ans;
    }
    i64* operator [] (const int& t) { return v[t]; }
    const i64* operator [] (const int& t) const { return v[t]; }

    friend istream& operator >> (istream& in, GeneralizedMatrix& x) {
        in >> x.m >> x.n;
        for (int i = 0; i < x.m; i++)
            for (int j = 0; j < x.n; j++)
                in >> x[i][j];
        return in;
    }
    friend ostream& operator << (ostream& out, const GeneralizedMatrix& x) {
        for (int i = 0; i < x.m; i++)
            for (int j = 0; j < x.n; j++)
                if (x[i][j] > -1e18) out << setw(4) << x[i][j] << " \n"[j == x.n - 1];
                else out << "-inf" << " \n"[j == x.n - 1];
        return out;
    }
};

vector<int> graph[N];
struct edge { int u, v; i64 w, b; } e[N];
int tot;

int fa[N], dep[N], siz[N], son[N], sonid[N], top[N], btn[N], dfn[N], rnk[N], cnt;
void dfs1(int u, int f) {
    fa[u] = f, son[u] = -1, siz[u] = 1;
    for (auto i : graph[u]) {
        int v = e[i].u ^ e[i].v ^ u;
        if (v == f) continue;
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        siz[u] += siz[v];
        if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v, sonid[u] = i;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    if (son[u] == -1) { btn[u] = u; return; }
    dfs2(son[u], t);
    btn[u] = btn[son[u]];
    for (auto i : graph[u]) {
        int v = e[i].u ^ e[i].v ^ u;
        if (v != son[u] && v != fa[u]) dfs2(v, v);
    }
}

i64 f[N][4], g[N][4];
multiset<i64> st[N], st2[N];
map<int, pair<i64, int>> inform[N], inform2[N];
void dfs(int u) {
    st[u].insert(0); st[u].insert(0);
    st2[u].insert(0);
    for (auto i : graph[u]) {
        int v = e[i].u ^ e[i].v ^ u;
        if (v == fa[u]) continue;
        i64 w = e[i].b - e[i].w;
        dfs(v);
        if (v == son[u]) continue;
        st[u].insert(max({0ll, f[v][2] + w, g[v][2] + w}));
        inform[u][v] = {max({0ll, f[v][2] + w, g[v][2] + w}), i};
        st2[u].insert(max(f[v][0], f[v][1]));
        inform2[u][v] = {max(f[v][0], f[v][1]), i};
    }
    if (~son[u]) {
        g[u][3] = *++st[u].rbegin();
        g[u][2] = *st[u].rbegin();
        g[u][1] = g[u][2] + g[u][3];
        g[u][0] = *st2[u].rbegin();
        f[u][2] = max(0ll, f[son[u]][3] + e[sonid[u]].b - e[sonid[u]].w);
        f[u][1] = max(f[u][2] + g[u][2], g[u][2] + g[u][3]);
        f[u][0] = max({f[son[u]][0], f[son[u]][1], g[u][0]});
        f[u][3] = max(f[u][2], g[u][2]);
    }
}

struct SegmentTree {
    struct TreeNode { int l, r; GeneralizedMatrix sum; } tr[N << 2];
    void pushup(int s) {
        tr[s].sum = tr[ls].sum * tr[rs].sum;
    }
    void calcMatrix(int s, int u) {
        if (~son[u]) {
            i64 w = e[sonid[u]].b - e[sonid[u]].w;
            tr[s].sum = GeneralizedMatrix(5, 5, -INF);
            tr[s].sum[0][0] = tr[s].sum[0][1] = 0, tr[s].sum[0][4] = g[u][0];
            tr[s].sum[1][3] = w + g[u][2], tr[s].sum[1][4] = g[u][2] + g[u][3];
            tr[s].sum[2][3] = w, tr[s].sum[2][4] = 0;
            tr[s].sum[3][3] = w, tr[s].sum[3][4] = g[u][2];
            tr[s].sum[4][4] = 0;
        }
        else tr[s].sum = GeneralizedMatrix(5);
    }
    void build(int l, int r, int s = 1) {
        tr[s].l = l, tr[s].r = r;
        if (l == r) {
            calcMatrix(s, rnk[l]);
            return;
        }
        int mid = l + r >> 1;
        if (l <= mid) build(l, mid, ls);
        if (mid < r) build(mid + 1, r, rs);
        pushup(s);
    }
    void modify(int p, int s = 1) {
        if (tr[s].l == tr[s].r) {
            calcMatrix(s, rnk[tr[s].l]);
            return;
        }
        int mid = tr[s].l + tr[s].r >> 1;
        if (p <= mid) modify(p, ls);
        else modify(p, rs);
        pushup(s);
    }
    GeneralizedMatrix query(int l, int r, int s = 1) {
        if (l <= tr[s].l && tr[s].r <= r) return tr[s].sum;
        int mid = tr[s].l + tr[s].r >> 1;
        GeneralizedMatrix ans = GeneralizedMatrix(5);
        if (l <= mid) ans = ans * query(l, r, ls);
        if (mid < r) ans = ans * query(l, r, rs);
        return ans;
    }
} T;

GeneralizedMatrix query(int u) {
    return T.query(dfn[u], dfn[btn[u]]) * GeneralizedMatrix(5, 1, 0);
}
void modify(int u, int v) {
    if (son[u] == v) {
        T.modify(dfn[u]);
        u = fa[top[u]];
        v = top[v];
    }
    while (~u) {
        auto& in = inform[u][v];
        auto& in2 = inform2[u][v];
        st[u].erase(st[u].find(in.ft));
        st2[u].erase(st2[u].find(in2.ft));

        auto mat = query(v);
        i64 w = e[in.se].b - e[in.se].w;
        st[u].insert(max({0ll, mat[2][0] + w, g[v][2] + w}));
        in.ft = max({0ll, mat[2][0] + w, g[v][2] + w});
        st2[u].insert(max(mat[0][0], mat[1][0]));
        in2.ft = max(mat[0][0], mat[1][0]);

        g[u][3] = *++st[u].rbegin();
        g[u][2] = *st[u].rbegin();
        g[u][1] = g[u][2] + g[u][3];
        g[u][0] = *st2[u].rbegin();
        T.modify(dfn[u]);
        v = top[u];
        u = fa[v];
    }
}

void work() {
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        ++tot;
        cin >> e[tot].u >> e[tot].v >> e[tot].w >> e[tot].b;
        graph[e[tot].u].emplace_back(tot);
        graph[e[tot].v].emplace_back(tot);
    }
    dfs1(1, -1);
    dfs2(1, 1);
    dfs(1);
    T.build(1, n);
    cout << max(f[1][0], f[1][1]) << endl;

    while (m--) {
        int x, y;
        cin >> x >> y;
        int u = e[x].u, v = e[x].v;
        if (dep[u] > dep[v]) swap(u, v);
        e[x].w = y;
        modify(u, v);
        auto mat = query(1);
        cout << max(mat[0][0], mat[1][0]) << endl;
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    //cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。

#pragma ... 是用来开启 O2、O3 等优化加快代码速度。

中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。

"" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。

ios::sync_with_stdio(false); (0); (0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。

将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。

秒客网