P7846 「dWoi R2」Arcade hall / 街机厅 题解

· · 题解

前言

继 P7238「DCOI」迷失森林 后本人写的第二篇树形 DP 的题解。（终于把比赛写挂的题写完了...）

若有错误，请指出。

本题考察了选手的各种优化技巧。

我一开始没有想到 \mathcal{O}(nR) 的算法，发现过不了，看了书虫的题解才明白。

本人觉得书虫的题解有点奇怪深奥（太蒻了，看的时候差点没看懂），自己写了一篇。

本题较 P7238「DCOI」迷失森林 较为简单，不过看看我的提交记录就知道有多坑了...

（这件事告诉我们：特判与初始化很重要）

好了，废话不多说，又双叒叕开始讲题了！

正文

第一问

我们分类讨论。

设 t 为连接 i 和其子节点 j 的边的边权。

1. t = 0

子节点可以选与父节点不一样的值，因此有 R - 1 种方案。

2. t = 1

子节点的值并没有要求，因此有 R 种方案。

3. t = 2

子节点的值必须与父节点一样，因此有 1 种方案。

于是将所有节点的值乘在一起，结果即为答案。

记得一开始乘个 R！

第二问

依旧分类讨论。

设 f_{i, j} 为第 i 个节点的点权为 j 时的最小值，则枚举的时候设 k 为子节点 son 的点权。

1. t = 0

子节点必须与父节点不同，因此将每个子节点选与父节点不同的值时的最小值累加即可。

f_{i, j} = \min_{k = 1, k \ne j}^R{\{f_{son, k}\}} + j

2. t = 1

子节点的值并没有要求，因此直接取个最小值。

f_{i, j} = \min_{k = 1}^R{\{f_{son, k}\}} + j

3. t = 2

子节点的值必须与父节点一样，只能从 f_{son, j} 转移而来。

f_{i, j} = f_{son, j} + j

则答案为 \min_{w = 1}^R{\{f_{Root, w}\}}，而树根 Root 可以随便选择，因此我们为了方便选 1 号节点为根。

小优化

如果你真这么写了，那么恭喜您拿到了部分分...

因为你枚举父子节点的点权要 \mathcal{O}(R^2)。

正解：

既然没有后效性，那就在做完一个节点以后记录一下当节点 i 的点权为 j 时最小值的前驱最小值与后继最小值，即前面的最小：

pre_{i, j} = \min_{k = 1}^{j - 1}{\{f_{i, j}\}} = \min{\{pre_{i, j - 1}, f_{i, j}\}}

以及后面的最小：

suf_{i, j} = \min_{k = j + 1}^{R}{\{f_{i, j}\}} = \min{\{suf_{i, j + 1}, f_{i, j}\}}

于是就将第二问中，t = 0 的动态转移方程改一下：

f_{i, j} = \min{\{pre_{i, j}, suf_{i, j}\}}

这样就不必枚举子节点的点权了，从而将复杂度降至 \mathcal{O}(R)，总共遍历 N 个节点，所以总共复杂度为 \mathcal{O}(nR)。

代码

你们最想要的..

Talk is\color{white}\text{n't} cheap, \color{white}\text{Don't} show me the code...

// Problem: P7846 「dWoi R2」Arcade hall / 街机厅
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7846
// Memory Limit: 512 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
#define MOD (unsigned long long)(1e9 + 7)
using namespace std;

struct Edge {
    unsigned long long nxt, to, dis;
} edge[200005];

unsigned long long cnt, ans = 1;
unsigned long long head[200005], f[100005][105], g[100005];
unsigned long long pref[100005][105], suff[100005][105], all[100005];
bool visited[100005];

unsigned long long N, R;

void add(unsigned long long u, unsigned long long v, unsigned long long w)
{
    ++ cnt;
    edge[cnt].to = v;
    edge[cnt].nxt = head[u];
    edge[cnt].dis = w;
    head[u] = cnt;
}

void dfs1(unsigned long long u)
{
    for(unsigned long long i = head[u]; i; i = edge[i].nxt)
    {
        unsigned long long v = edge[i].to, w = edge[i].dis;
        if(visited[v]) continue;
        visited[v] = true;
        if(w == 0)      g[v] = R - 1;
        else if(w == 1) g[v] = R;
        else if(w == 2) g[v] = 1;
        else puts("114514");
        ans = ((ans % MOD) * (g[v] % MOD)) % MOD;
        dfs1(v);
    }
}

void dfs2(unsigned long long u)
{
    for(unsigned long long i = 1; i <= R; ++ i)
        f[u][i] = i;

    for(unsigned long long i = head[u]; i; i = edge[i].nxt)
    {
        unsigned long long v = edge[i].to, w = edge[i].dis;
        if(visited[v]) continue;
        visited[v] = true;
        dfs2(v);
        if(w == 0)
            for(unsigned long long j = 1; j <= R; ++ j)
                f[u][j] += min(pref[v][j - 1], suff[v][j + 1]);

        if(w == 1)
            for(unsigned long long j = 1; j <= R; ++ j)
                f[u][j] += all[v];

        if(w == 2)
            for(unsigned long long j = 1; j <= R; ++ j)
                f[u][j] += f[v][j];
    }

    pref[u][0] = LONG_LONG_MAX;
    suff[u][R + 1] = LONG_LONG_MAX;
    all[u] = LONG_LONG_MAX;
    for(unsigned long long i = 1; i <= R; ++ i)
        pref[u][i] = min(pref[u][i - 1], f[u][i]);

    for(unsigned long long i = R; i >= 1; -- i)
        suff[u][i] = min(suff[u][i + 1], f[u][i]);

    for(unsigned long long i = 1; i <= R; ++ i)
        all[u] = min(all[u], f[u][i]);
}

signed main()
{
    srand(time(0));
    cin >> N >> R;
    bool flag = false;
    for(unsigned long long i = 1; i < N; ++ i)
    {
        unsigned long long u, v, t;
        cin >> u >> v >> t;
        add(u, v, t);
        add(v, u, t);
        if(!t)
            flag = true;
    }

    ans *= R;
    unsigned long long Root = rand() % N;
    visited[Root] = true;
    dfs1(Root);
    if(R == 1 && flag)
    {
        cout << "0 0";
        return 0;
    }
    else
    {
        cout << ans << ' ';
    }

    memset(visited, 0, sizeof(visited));
    visited[Root] = true;
    dfs2(Root);
    ans = LONG_LONG_MAX;
    for(unsigned long long i = 1; i <= R; ++ i)
        ans = min(ans, f[Root][i]);

    cout << ans << endl;
    return 0;
}

后言

这里感谢毒瘤出题人！

本题 DP 难度不大，不过需要加点优化，希望每一位读者都能够学好树形 DP（以后把我吊打）。