CSP-S2022题解

2022秋

---

[CSP2022 T3] 星战

Description

Solution

神奇的随机化题。

考虑询问的两个条件：

简单来说就是 所有点出度为 $1$ 且 都可以走到环上

其实这样的图有个名称，叫 内向基环树森林，而一张图是内向基环树森林的充要条件就是 所有点出度为1

所以第二个条件实际上是无用的，我们只需要考虑第一个条件，这点在考场上稍微手玩一下也能看出来。

然后大概有两类想法：

$1^o$ Sum Hash

考虑这样一个等价一一对应的想法：

所有点出度为 $1$ $\Longleftrightarrow$ 所有点出度和为 $n$

但这显然是错的，他显然是个充分但不必要的逻辑。

例如，出度为 $1 + 1$ 的图 与出度为 $2 + 0$ 的图，这样的情况显然会出问题。

换句话说，其实是这个出度和 $Sum$，他可以被组合出来的形式太多，而我们要求的所有点的出度形式太特殊了。

同时，我们做的是一个类似一一对应的操作，而问题也正出在对应存在冲突上，这都很满足 hash 的特点。

所以有一个想法：

我们随机给点赋权值，令 $w(u)$ 表示所有连向 $u$ 的点的点权和，$Sum(u)$ 表示整个图所有点的点权和

那么上述的一一对应关系可以转化为：

$$Sum(u) = \sum{w(u)}$$

满足这个条件，我们就认为它满足题意。

四个操作显然都非常好维护。

$2^o$ 一种奇怪的做法

咕咕咕。

Code

//The Code Is From Dawn

[CSP2022 T4] 数据传输

Description

此题解参考GraphCity的blog

请大家点个赞bushi

Solution

暂时省略一些部分分做法。

我们直接来讨论一下 $k = 1/2/3$ 的情况。

首先对于 $k = 1$ ：

显然答案就是两点之间路径点权和，树剖或者倍增维护即可。

对于 $k = 2$ ：

我们开始仔细分析此题的一些性质。

首先要提出一个很重要的思考点，最优的方案是否会走出两点之间的路径

这是影响这题重要的问题，可以稍微手玩一下。

至少我们能大概猜出，即使走出了两点的路径，也不会走得特别偏。

所以不妨先大胆猜测，最优方案一定在两点间的路径上

对于 $k = 2$，可以证明这是对的。

那么可以考虑 DP，设 $f[i]$ 表示跳到点 $i$ 的最小答案。

显然有

$$f[i] = min(f[i - 1], f[i - 2]) + a[i]$$

我们先不考虑如何优化。

对于 $k = 3$：

我们发现之前的结论被推翻了。

当 $k = 3$ 时，你可以从一个点 $x$ 的儿子，跳到与他相邻的其他儿子，而这有可能成为更优的情况。

我们考虑修正一下这个结论，发现即使要跳出这条链，最多也只会跳到 $x$ 点的唯一一个儿子，而这个儿子显然应该是点权最小的。

我们记：$x$ 的儿子最小点权为 $num[x]$

再修改一下状态，$f[i][0/1]$ 表示跳到点 $i$，是否跳出这条链的答案。

$$f[i][0] = \min{(f[i - 1][0], f[i - 2][0], f[i - 2][1], f[i - 3][0]) +1}$$

$$f[i][1] = \min{\begin{cases}f[i][0] + num[i]\\\min{(f[i - 1][0], f[i - 1][1], f[i - 1][2]) + num[i]}\end{cases}}$$

至此可以拿到 $76pts$ 的好成绩。

考虑优化。

我们从 $k = 2$ 的方程入手。

$$f[i] = min(f[i - 1], f[i - 2]) + 1$$

带取 $\min$ 与 加和的线性方程，有没有想到什么？

NOIP2018 保卫王国

他显然可以用 DDP，而且他不带修！

Graphcity 的 DDP 浅谈

我们把 $k = 3$ 的方程重新构造一下。

我们发现他只与要跳到的点与 $x$ 的距离有关。

设：$f[i][0/1/2]$ 表示 跳到距离点$i$ 为 $0/1/2$ 的答案。

$$f[i][0] = \min{(f[i - 1][0], f[i - 1][1], f[i - 1][2])} + a[i]$$

$$f[i][1] = \min{(f[i - 1][0], f[i - 1][1] + num[i], f[i - 1][2] + a[i] + num[i])}$$

$$f[i][2] = f[i - 1][1]$$

然后把三种情况都用矩阵表示：略。

然后直接把这个转移矩阵倍增出来，就解决了此题。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2 * 1e5 + 5, INF = 1e18 + 7;
int n, Q, K;
int Val[maxn], num[maxn], f[maxn][25];
struct node {
    int v, nex;
}edge[maxn << 1];
int head[maxn], len, Dep[maxn];
inline void make_map(int u, int v) {
    len++;
    edge[len].nex = head[u];
    edge[len].v = v;
    head[u] = len;
}
struct Matrix {
    int num[3][3];
    inline void Clear() {
        for(register int i = 0; i < 3; ++i)
            for(register int j = 0; j < 3; ++j) num[i][j] = INF;
    }
    inline void Out() {
        for(register int i = 0; i < 3; ++i) {
            for(register int j = 0; j < 3; ++j) printf("%lld ", num[i][j]);
            printf("\n");
        }
    }
    inline int& operator() (int i, int j) { return num[i][j]; }
}Base[maxn], Up[maxn][25], Down[maxn][25];
inline Matrix Init(int op = 0, int id = 0) {
    Matrix A; A.Clear();
    if(!op) {
        for(register int i = 0; i < 3; ++i) A(i, i) = 0;
    }
    else if(op == 1){
        if(K == 1) A(0, 0) = Val[id], A(1, 1) = A(2, 2) = 0;
        if(K == 2) A(0, 0) = A(0, 1) = Val[id], A(1, 0) = A(2, 2) = 0;
        if(K == 3) {
            A(0, 0) = A(0, 1) = A(0, 2) = Val[id];
            A(1, 0) = 0, A(1, 1) = num[id], A(1, 2) = num[id] + Val[id];
            A(2, 1) = 0;
        }
    }
    else {
        for(register int i = 0; i < 3; ++i) A(i, i) = 0;
        A(0, 0) = Val[id];
        if(K == 3) A(0, 1) = Val[id] + num[id];
    }
    return A;
}
inline Matrix operator * (Matrix A, Matrix B) {
    Matrix C; C.Clear();
    for(register int i = 0; i < 3; ++i)
        for(register int j = 0; j < 3; ++j)
            for(register int k = 0; k < 3; ++k) C(i, j) = min(C(i, j), A(i, k) + B(k, j));
    return C;
}
inline void Search(int x, int fa) {
    f[x][0] = fa, Up[x][0] = Down[x][0] = Base[x], Dep[x] = Dep[fa] + 1;
    for(register int i = 1; i <= 20; ++i) {
        f[x][i] = f[f[x][i - 1]][i - 1];
        Up[x][i] = Up[f[x][i - 1]][i - 1] * Up[x][i - 1];
        Down[x][i] = Down[x][i - 1] * Down[f[x][i - 1]][i - 1];
    }
    for(register int i = head[x]; i; i = edge[i].nex) {
        int y = edge[i].v;
        if(y == fa) continue;
        Search(y, x);
    }
}
inline Matrix LCA(int x, int y) {
    Matrix A = Init(), B = Init();
    if(Dep[x] < Dep[y]) B = Base[y], y = f[y][0];
    for(register int i = 20; i >= 0; --i) {
        if(Dep[f[x][i]] >= Dep[y]) A = Up[x][i] * A, x = f[x][i];
        if(x == y) return B * Base[x] * A;
    }
    for(register int i = 20; i >= 0; --i)
        if(f[x][i] != f[y][i]) A = Up[x][i] * A, B = B * Down[y][i], x = f[x][i], y = f[y][i];
    B = B * Base[y] * Base[f[y][0]], A = Base[x] * A;
    return B * A;
}
inline bool cmp(int x, int y) { return Val[x] < Val[y]; }
inline int Solve(int x, int y) {
    if(x == y) return Val[x];
    if(Dep[x] < Dep[y]) swap(x, y);
    Matrix Answer = LCA(f[x][0], y) * Init(2, x);
    return Answer(0, 0);
}
signed main() {
    #ifndef ONLINE_JUDGE    
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
    #endif
    n = read(), Q = read(), K = read();
    for(register int i = 1; i <= n; ++i) Val[i] = read(), num[i] = INF;
    for(register int i = 1; i < n; ++i) {
        int u = read(), v = read();
        make_map(u, v), make_map(v, u), num[u] = min(num[u], Val[v]), num[v] = min(num[v], Val[u]);
    }
    for(register int i = 1; i <= n; ++i) Base[i] = Init(1, i);
    Search(1, 0);
    while(Q--) {
        int u = read(), v = read();
        printf("%lld\n", Solve(u, v));
    }
    return 0;
}