P6803 [CEOI2020]星际迷航

滑蒻稽 · 2022-03-08 10:24:34 · 题解

Des

P6803 [CEOI2020]星际迷航

Sol

首先设败点为先手必败的点，胜点为先手必胜的点。记胜点 dp_u=1，败点 dp_u=0。

在不同树之间连边相当于给被连上的树换一个根。

如果一个点接上一个败点，那么自己有可能变成胜点，从而导致根的胜负情况发生逆转（变成胜点或败点都有可能）。如果一个点接上一个胜点那么没有影响。

于是换根 DP 求出有多少个点连接败点后会使根的胜负情况发生逆转，记为 R_u。

记整棵树败点数目为 c，考虑 D=1 的情况。如果 1 号点是胜点，那么答案为 (n-R_1)\times c+(n-c)\times n；如果 1 号点是败点，那么答案为 R_1\times c。

然后考虑 D=2 的情况。设以第二棵树败点的答案总和为 f0，胜点答案总和为 f1。那么对于第 0 颗树的根，如果根是胜点，那么答案为 (n-R_1)f0+nf1。如果根是败点，那么答案为 R_1f0。

考虑 f0,f1 怎么求。f0 可能由胜点转败点或败点不变组成，f1 同理。于是有

对于 D=3 的情况，第一棵树的 f0',f1' 可以用第二棵树的 f0,f1 迭代得到，只需把上面公式中的 c 替换为 f0，n-c 替换为 f1。D 更大的情况可以用矩阵快速幂优化。

我们设转移矩阵为 T，算出 T^{D-1}\times \begin{matrix}[c&n-c]\end{matrix} 得到 \begin{matrix}[f0&f1]\end{matrix}。再根据一号点是胜点还是败点输出答案为 (n-R_1)\times f0+n\times f1 或 R_1\times f0 即可。

然后讲一下换根 DP。R_u 的值在两种 情况下不为 0。一是节点全都是败点，这样 R_u 就等于所有儿子 R_v 之和。二是节点恰有一个为败点，这样 R_u 就等于该点 R_v。于是只需要维护儿子败点的数量即可换根 DP。

最后复杂度 O(n+\log D)。

这道题比较麻烦地方在于 R_u 的设置。如果分根从胜点变败点和从败点变胜点处理，那你大概就要写两个 换根 DP，比较麻烦。但用 R_u 表示 u 的胜负逆转后就变得简单了。

My Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5, D = 1e9 + 7;
inline void Add(int &a, ll b) { a = (a + b) % D; }
int n, c;
ll K;
struct mat {
    int a[2][2];
    mat(bool e = false) {
        memset(a, 0, sizeof a);
        if(e) a[0][0] = a[1][1] = 1;
    }
    mat operator*(const mat &x) {
        mat y;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                y.a[i][j] = ((ll)a[i][0] * x.a[0][j] + (ll)a[i][1] * x.a[1][j]) % D;
        return y;
    }
};
mat fpm(mat a, ll b) {
    mat res(true);
    while(b) {
        if(b & 1) res = res * a;
        b >>= 1, a = a * a;
    }
    return res;
}
vector<int> g[N];
int dp[N], s0[N], R[N], SR[N][2];
// SR[i][0] 表示 i 号点所有 dp 值为 0 的儿子的 R 的和，SR[i][1] 同理 
void dfs1(int u, int f) {
    for(int v : g[u]) {
        if(v == f) continue;
        dfs1(v, u);
        s0[u] += !dp[v];
        SR[u][dp[v]] += R[v];
    }
    dp[u] = (s0[u] > 0);
    if(s0[u] == 1) R[u] = SR[u][0];
    else if(s0[u] == 0) R[u] = SR[u][1] + 1;
}
int dp2[N], R2[N];
// 换根 DP 
void dfs2(int u, int f) {
    if(!dp[u]) ++c;
    R2[u] = R[u], dp2[u] = dp[u];
    for(int v : g[u]) {
        if(v == f) continue;
        int s0u = s0[u], dpu = dp[u], Ru = R[u], SRu0 = SR[u][0], SRu1 = SR[u][1];
        int s0v = s0[v], dpv = dp[v], Rv = R[v], SRv0 = SR[v][0], SRv1 = SR[v][1];

        s0[u] -= !dp[v];
        dp[u] = (s0[u] > 0);
        SR[u][dp[v]] -= R[v];
        if(s0[u] == 1) R[u] = SR[u][0];
        else if(s0[u] == 0) R[u] = SR[u][1] + 1;
        else R[u] = 0;
        dp[v] |= !dp[u];
        s0[v] += !dp[u];
        SR[v][dp[u]] += R[u];
        if(s0[v] == 1) R[v] = SR[v][0];
        else if(s0[v] == 0) R[v] = SR[v][1] + 1;
        else R[v] = 0;
        dfs2(v, u);

        s0[u] = s0u, dp[u] = dpu, R[u] = Ru, SR[u][0] = SRu0, SR[u][1] = SRu1;
        s0[v] = s0v, dp[v] = dpv, R[v] = Rv, SR[v][0] = SRv0, SR[v][1] = SRv1;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> K;
    for(int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].emplace_back(v), g[v].emplace_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 0);

    mat p, T;
    // 处理转移矩阵 
    for(int i = 1; i <= n; i++) {
        if(dp2[i] == 0) {
            Add(T.a[0][0], n - R2[i]);
            Add(T.a[1][0], n);
            Add(T.a[0][1], R2[i]);
        } else if (dp2[i] == 1) {
            Add(T.a[0][0], R2[i]);
            Add(T.a[0][1], n - R2[i]);
            Add(T.a[1][1], n);
        }
    }
    p.a[0][0] = c, p.a[0][1] = n - c;
    p = p * fpm(T, K - 1);

    int f0 = p.a[0][0], f1 = p.a[0][1];
    if(dp[1]) cout << ((ll)(n - R2[1]) * f0 + (ll)n * f1) % D << '\n';
    else cout << (ll)R2[1] * f0 % D << '\n';

    return 0;
}