「dWoi R2」Arcade hall / 街机厅

GitHub 跳转原题关系图返回列表

先用并查集缩掉所有 t=2 的相等点，再只保留 t=0 的不同色森林；计数是森林染色，最小和是带点权二分染色。

OJ: luogu

题目 ID: P7846

难度:提高+/省选-

标签:并查集树图论计数二分图染色

日期: 2026-06-21 03:40

题意

给一棵树，每条边有三种关系：

$0$ ：两端点权必须不同
$1$ ：没有要求
$2$ ：两端点权必须相同

每个点权 $w_i$ 都在 $[1,R]$ 内。

要求输出：

合法序列数量（对 $10^9+7$ 取模）
所有合法序列里 $\sum w_i$ 的最小值；若无解输出 $0$

思路

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;
const long long MOD = 1000000007LL;

int n, r_limit;
int eu[MAXN], ev[MAXN], et[MAXN];
int w[MAXN];
long long ways;
long long best_sum;

void dfs(int u) {
    if (u > n) {
        for (int i = 1; i < n; i++) {
            if (et[i] == 0 && w[eu[i]] == w[ev[i]]) {
                return;
            }
            if (et[i] == 2 && w[eu[i]] != w[ev[i]]) {
                return;
            }
        }

        ways = (ways + 1) % MOD;
        long long sum = 0;
        for (int i = 1; i <= n; i++) {
            sum += w[i];
        }
        best_sum = min(best_sum, sum);
        return;
    }

    for (int val = 1; val <= r_limit; val++) {
        w[u] = val;
        dfs(u + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力枚举所有点权，检查约束并统计答案。
    cin >> n >> r_limit;
    for (int i = 1; i < n; i++) {
        cin >> eu[i] >> ev[i] >> et[i];
    }

    ways = 0;
    best_sum = (1LL << 60);
    dfs(1);

    if (ways == 0) {
        cout << 0 << ' ' << 0 << '\n';
    } else {
        cout << ways % MOD << ' ' << best_sum << '\n';
    }
    return 0;
}

brute.cpp 直接枚举所有点权，再检查每条边的约束。这个做法完全正确，但复杂度是 $R^n$ ，只能处理很小的数据。

真正的关键是先把三种边分开看。

$t=2$ 表示两端必须相等，所以可以先把这些点全部缩成一个并查集块。

缩点后：

每个新点对应一个“必须取同一个值”的块
这个块的权重就是它包含多少个原点

再看剩余边：

$t=1$ 没有限制，可以直接忽略
$t=0$ 只要求两个块取值不同

这样问题就被化成了一片森林上的约束。

缩点后的理解

这张图展示的是：先把 $t=2$ 边缩掉，剩下只有“必须不同”的边真正有约束。

graph G {
  A [label="一个缩点块"];
  B [label="另一个缩点块"];
  A -- B [label="t=0"];
}

缩点块内部所有原点必须同值，所以内部不再需要单独讨论。剩下的 $t=0$ 边只是在这些块之间做“不同色”限制。

第一问就变成森林 proper coloring 计数。

对于一个 $t=0$ 连通块：

第一个点有 $R$ 种选法
之后每条边往下扩展时都有 $R-1$ 种

所以若这个连通块有 $s$ 个缩点，方案数就是：

$R \cdot (R-1)^{s-1}$

所有连通块相乘即可。

第二问则更简单。

因为森林一定是二分图，所以想让总和最小，只需要使用最小的两种值 $1$ 和 $2$ 。设某个连通块二分染色后两侧原点数总和分别是 $A,B$ ，那么：

一侧放 $1$
另一侧放 $2$

最优代价就是：

$A + B + \min(A, B)$

也就是让较大的那一侧用 $1$ ，较小的一侧用 $2$ 。

对于没有任何 $t=0$ 约束的孤立块，直接全部取 $1$ 即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;
const long long MOD = 1000000007LL;

struct Edge {
    int u, v, t;
};

int n, r_limit;
Edge edges[MAXN];

int dsu_parent[MAXN];
int dsu_size[MAXN];
int comp_id[MAXN];
int comp_weight[MAXN];
int comp_cnt;

vector<int> g[MAXN];
int color_part[MAXN];

int find_root(int x) {
    if (dsu_parent[x] == x) {
        return x;
    }
    dsu_parent[x] = find_root(dsu_parent[x]);
    return dsu_parent[x];
}

void unite(int a, int b) {
    a = find_root(a);
    b = find_root(b);
    if (a == b) {
        return;
    }
    if (dsu_size[a] < dsu_size[b]) {
        swap(a, b);
    }
    dsu_parent[b] = a;
    dsu_size[a] += dsu_size[b];
}

long long mod_pow(long long a, int e) {
    long long res = 1;
    while (e > 0) {
        if (e & 1) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> r_limit;
    for (int i = 1; i <= n; i++) {
        dsu_parent[i] = i;
        dsu_size[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].t;
        if (edges[i].t == 2) {
            unite(edges[i].u, edges[i].v);
        }
    }

    for (int i = 1; i <= n; i++) {
        comp_id[i] = 0;
        comp_weight[i] = 0;
        g[i].clear();
        color_part[i] = -1;
    }

    for (int i = 1; i <= n; i++) {
        int root = find_root(i);
        if (comp_id[root] == 0) {
            comp_id[root] = ++comp_cnt;
        }
        int id = comp_id[root];
        comp_weight[id]++;
    }

    int zero_edge_cnt = 0;
    for (int i = 1; i < n; i++) {
        if (edges[i].t != 0) {
            continue;
        }
        int a = comp_id[find_root(edges[i].u)];
        int b = comp_id[find_root(edges[i].v)];
        // 在树上缩掉 t=2 后，不会出现 a == b 的情况；这里保守防一下。
        if (a == b) {
            cout << 0 << ' ' << 0 << '\n';
            return 0;
        }
        g[a].push_back(b);
        g[b].push_back(a);
        zero_edge_cnt++;
    }

    if (r_limit == 1 && zero_edge_cnt > 0) {
        cout << 0 << ' ' << 0 << '\n';
        return 0;
    }

    long long ways = 1;
    long long min_sum = 0;
    for (int i = 1; i <= comp_cnt; i++) {
        if (color_part[i] != -1) {
            continue;
        }

        long long part_sum[2] = {0, 0};
        int edge_in_component = 0;
        queue<int> q;
        q.push(i);
        color_part[i] = 0;

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            part_sum[color_part[u]] += comp_weight[u];
            edge_in_component += (int)g[u].size();

            for (size_t j = 0; j < g[u].size(); j++) {
                int v = g[u][j];
                if (color_part[v] == -1) {
                    color_part[v] = color_part[u] ^ 1;
                    q.push(v);
                }
            }
        }

        if (edge_in_component == 0) {
            // 没有敌对边约束的独立点，直接放最小值 1 即可。
            ways = ways * r_limit % MOD;
            min_sum += part_sum[0];
        } else {
            int edge_cnt = edge_in_component / 2;
            ways = ways * r_limit % MOD;
            ways = ways * mod_pow(r_limit - 1, edge_cnt) % MOD;
            // 这个连通块一定是树，最优只需要用颜色 1 和 2，
            // 再把较小的一侧放颜色 2。
            min_sum += part_sum[0] + part_sum[1] + min(part_sum[0], part_sum[1]);
        }
    }

    cout << ways % MOD << ' ' << min_sum << '\n';
    return 0;
}

复杂度

并查集、建图、染色都只需要线性级别处理。

总时间复杂度是 $O(n \alpha(n))$ ，空间复杂度是 $O(n)$ 。

总结

这题最核心的拆分是：

$t=2$ 先缩点
$t=1$ 直接忽略
$t=0$ 变成森林上的不同色约束

这样第一问变成森林染色计数，第二问变成带点权二分染色最小代价。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7846 「dWoi R2」Arcade hall / 街机厅

题目背景

众所周知，才囚学院地下有一个街机厅，~~百田被星龙马打败了 114514 次~~。

百田不服气，于是他打开了一个单人游戏 —— 先辈的城市。

114514 年，火星，幺舅幺舅巴以灵国。

因为有小可爱提出题面过于冗长，所以下方有 简要题面。

题目描述

幺舅幺舅巴以灵国一共有 $n$ 个城市，他们之间用一种神奇的通讯工具 —— 先辈符，第 $i$ 个城市的先辈符上刻有一个正整数 $w_i$ 。这 $n$ 个城市之前有 $n-1$ 条道路，第 $j$ 条道路连接第 $u_j$ 个城市和第 $v_j$ 个城市，有一个属性 $t_j$ ，这一条道路就表示为 $(u_j,v_j,t_j)$ ，其中 $t_j \in \{0,1,2\}$ ，意为：

$t_j=0$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是敌对关系；
$t_j=1$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是平等关系；
$t_j=2$ 时，第 $u_j$ 个城市与第 $v_j$ 个城市是友好关系。

每一条道路都是双向的，并且保证任意两个城市 $u,v$ 之间都是可以互相到达的。

最近火星发生了 MARS-514 病毒疫情，先辈符系统的修建要加快脚步。我们规定：

$w_i \in [1,R]$ ，且是一个正整数；
对于一条道路 $(p,q,r)$ ，有如下要求：
- 当 $r=0$ 时，即第 $p$ 个城市与第 $q$ 个城市处于敌对关系时，需要保证 $w_p \ne w_q$ ；
- 当 $r=2$ 时，即第 $p$ 个城市与第 $q$ 个城市处于友好关系时，需要保证 $w_p=w_q$ ；
- 当 $r=1$ 时，即第 $p$ 个城市与第 $q$ 个城市处于平等关系时，不需要保证 $w_p$ 与 $w_q$ 的大小关系。

求这样分配 $w_i$ 后，将 $w_i$ 作为一个序列，会形成多少个本质不同的序列 $w_i$ 。

额外地，幺舅幺舅巴以灵国的统治者浩二结节在建造先辈符发现 $w_i$ 越大，用墨就会越多，建造起来也会越困难，所以浩二结节想知道 $w_i$ 的和的最小值是多少。

注意，本题的序列 $A_i$ 与 $B_i$ 本质相同当且仅当对于所有 $i$ 都有 $A_i=B_i$ 。

本质不同即为不满足本质相同的两个序列。

简要题面：

有一棵 $n$ 个点的树，第 $i$ 个点有点权 $w_i$ ，第 $j$ 条边有边权 $t_j$ ；
每一条边 $(u_j,v_j,t_j)$ 两边点的点权有如下要求：
- $t_j=0$ ， $w_{u_j} \ne w_{v_j}$ ；
- $t_j=1$ ，没有要求；
- $t_j=2$ ， $w_{u_j}=w_{v_j}$ ；
- 对任意点权都要有 $w_i \in [1,R]$ ；
求当 $w_i$ 作为序列时，一共有多少种本质不同的序列 $w_i$ 以及 $w_i$ 的和的最小值。

输入格式

第一行两个整数 $n,R$ 代表城市数与值域。

接下来 $n-1$ 行每行三个整数 $u_j,v_j,t_j$ 描述一条道路。

输出格式

一行两个整数分别代表满足要求的本质不同的序列 $w_i$ 的个数和 $w_i$ 的和的最小值。

如果不存在本质不同的序列（即第一问答案为 $0$ ），第二问也请输出一个 $0$ 。

只有第一问答案对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

text

输出 #1

text

112 4

输入输出样例 #2

输入 #2

text

输出 #2

text

1648 12

说明/提示

样例 1 解释

样例中的道路分布如下：

一共有 $12$ 种赋值方式：

$w_i=\{1,2,2\}$ ；
$w_i=\{1,2,3\}$ ；
$w_i=\{1,3,2\}$ ；
$w_i=\{1,3,3\}$ ；
$w_i= \bf \{2,1,1\}$ ，这是最优情况；
$w_i=\{2,1,3\}$ ；
$w_i=\{2,3,1\}$ ；
$w_i=\{2,3,3\}$ ；
$w_i=\{3,1,1\}$ ；
$w_i=\{3,1,2\}$ ；
$w_i=\{3,2,1\}$ ；
$w_i=\{3,2,2\}$ 。

样例 2 解释

样例中的道路分布如下：

对于第二问，其中一种最优的赋值方式是： $w_i=\{2,1,1,1,1,1,2,1,2\}$ 。

数据规模与约定

本题采用捆绑测试。

Subtask 1（5 pts）： $t_j=1$ 或 $t_j=2$ ；
Subtask 2（5 pts）： $R=1$ ；
Subtask 3（10 pts）： $u_j=j$ ， $v_j=j+1$ ；
Subtask 4（20 pts）： $t_j=0$ ；
Subtask 5（10 pts）： $n \le 10$ ， $R \le 5$ ；
Subtask 6（50 pts）：无特殊限制。

对于 $100\%$ 的数据， $1 \le n \le 10^5$ ， $1 \le R \le 100$ 。

对于 Subtask 1 ~ 5， $R \le 40$ 。

上面描述 Subtask 时 $t_j=P$ 即为对于所有 $j \in [1,n)$ 都有 $t_j=P$ 。

其中对于 Subtask 1，“或” 意为 Subtask 1 的一部分测试点满足 $t_j=1$ ，另一部分测试点满足 $t_j=2$ 。

「dWoi R2」Arcade hall / 街机厅

目录

题意

思路

缩点后的理解

代码

复杂度

总结

一图流解析