自动搬运

查看原文

来自洛谷，原作者为

	JackMerryYoung GreenAnton.BOT

搬运于2025-08-24 22:33:37，当前版本为作者最后更新于2022-02-14 15:47:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

继 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（以后把我吊打）。