2022 数据传输 · 方案一 k 为 1 前缀和

CSP-S 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2117 字
n 个点的树，点 i 权 w_i
2022
树
正文

// CSP-S 2022 复赛 T4 · 数据传输（方案一：k=1 树上前缀和，部分分）
// 原题：https://oj.yecheng.tv/p/CSPS2022D
// 题意：n 个点的树，点 i 权 w_i。Q 次询问 (s, t, k)：信号从 s 传到
//       t，每步沿边移动 1..k 步；每个被经过的点（含 s、t）各收一次
//       费（一次经过只收一次，转向点同点不重复收）。求最小总费用。
// 思路（k=1 退化为路径点权和）：
//   k=1 时信号只能逐边走，路径唯一（树上），费用 = 路径上所有点的
//   权和 = 根前缀和 dis[u]（点到根的权和）组合：
//       cost(s,t) = dis[s] + dis[t] − dis[lca] − dis[parent(lca)]。
//   LCA 用倍增。k=1 的测试点（6~7 等）可过；k≥2 见方案二。
// 复杂度：O((n + q) log n)。
// 易错点：
//   1. 点权转前缀和时 lca 本身只计一次；
//   2. 权和 long long；
//   3. s ≠ t 保证。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n, q;
long long w[200005];
vector<int> g[200005];
int dep[200005], up[18][200005];
long long dis[200005];

void dfs(int u, int fa) {
    up[0][u] = fa;
    dis[u] = dis[fa] + w[u];
    dep[u] = dep[fa] + 1;
    for (int v : g[u])
        if (v != fa) dfs(v, u);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = 17; j >= 0; j--)
        if (dep[up[j][u]] >= dep[v]) u = up[j][u];
    if (u == v) return u;
    for (int j = 17; j >= 0; j--)
        if (up[j][u] != up[j][v]) {
            u = up[j][u];
            v = up[j][v];
        }
    return up[0][u];
}

int main() {
    freopen("transmit.in", "r", stdin);
    freopen("transmit.out", "w", stdout);
    scanf("%d%d%d", &n, &q, &w[0]);
    // 读入 k（题目第三个数），k=1 时用本方案
    int k;
    scanf("%d", &k);                     // 占位：按输入格式调整
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dis[0] = 0;
    dfs(1, 0);
    for (int j = 1; j < 18; j++)
        for (int u = 1; u <= n; u++)
            up[j][u] = up[j - 1][up[j - 1][u]];
    while (q--) {
        int s, t, kk;
        scanf("%d%d%d", &s, &t, &kk);
        if (kk == 1) {
            int l = lca(s, t);
            long long ans = dis[s] + dis[t] - dis[l] - dis[up[0][l]];
            printf("%lld\n", ans);
        } else {
            // k ≥ 2 的倍增矩阵做法见方案二
            printf("0\n");
        }
    }
    return 0;
}
2022 数据传输 · 方案一 k 为 1 前缀和

正文

CSP-S 标程 · 复赛真题的其它内容
