链接: https://codeforces.com/problemset/problem/1244/D
题意: 给一个树染上三种颜色, 保证每一段长度为 3 的链颜色都不相同.
题解: 颜色很少可以发现, 当且仅当这个树是一条链的时候才满足条件 (记录度数即可), 对这条链进行暴力染色即可, 确定前三个即可确定整条链.
- #include <bits / stdc++.h> #define IO_read iOS: :sync_with_stdio(false);
- cin.tie(0)#define fre freopen("in.txt", "r", stdin)#define _for(i, a, b) for (int i = a; i <b; i++)#define _rep(i, a, b) for (int i = a; i <= b; i++)#define lowbit(a)((a) & -(a)) using namespace std;
- typedef long long ll;
- template < class T> void read(T & x) {
- char c;
- bool op = 0;
- while (c = getchar(), c <'0' || c> '9') if (c == '-') op = 1;
- x = c - '0';
- while (c = getchar(), c>= '0' && c <= '9') x = x * 10 + c - '0';
- if (op) x = -x;
- }
- template <class T> void write(T x) {
- if (x <0) putchar('-'),
- x = -x;
- if (x>= 10) write(x / 10);
- putchar('0' + x % 10);
- }
- const int maxn = 1e5 + 5;
- int n,
- tot,
- degree[maxn],
- head[maxn];
- int cost[4][maxn];
- struct Edge {
- int to,
- next;
- }
- edge[maxn * 2];
- void addedge(int u, int v) {
- edge[++tot].to = v;
- edge[tot].next = head[u];
- head[u] = tot;
- }
- int rt,
- color[maxn];
- ll ans = (ll) 1 <<61;
- bool check() {
- for (int i = 1; i <= n; i++) if (degree[i]>= 3) return true;
- return false;
- }
- void find_rt() {
- for (int i = 1; i <= n; i++) if (degree[i] == 1) {
- rt = i;
- break;
- }
- }
- int dfsn[maxn],
- cnt_dfs;
- void dfs(int u, int fa) {
- dfsn[++cnt_dfs] = u;
- for (int i = head[u]; i != -1; i = edge[i].next) {
- int v = edge[i].to;
- if (v == fa) continue;
- dfs(v, u);
- }
- }
- int COLOR[4] = {
- 0,
- 1,
- 2,
- 3
- };
- int first,
- second,
- third;
- void solve() {
- find_rt();
- dfs(rt, 0);
- do {
- ll res = 0;
- for (int i = 1; i <= n; i++) {
- int v = dfsn[i];
- color[v] = COLOR[(i - 1) % 3 + 1];
- res += cost[color[v]][v];
- //printf("! v=%d, color=%d, cost=%d\n", v, color[v], cost[color[v]][v]);
- }
- //printf("\n");
- if (res <ans) {
- first = COLOR[1],
- second = COLOR[2],
- third = COLOR[3];
- ans = res;
- }
- } while ( next_permutation ( COLOR + 1 , COLOR + 4 ));
- COLOR[1] = first,
- COLOR[2] = second,
- COLOR[3] = third;
- for (int i = 1; i <= n; i++) {
- int v = dfsn[i];
- color[v] = COLOR[(i - 1) % 3 + 1];
- }
- }
- int main() {
- IO_read;
- cin>> n;
- for (int i = 1; i <= 3; i++) for (int j = 1; j <= n; j++) cin>> cost[i][j];
- memset(head, -1, sizeof(head));
- for (int i = 1, u, v; i <n; i++) {
- cin>> u>> v;
- addedge(u, v);
- addedge(v, u);
- degree[u]++,
- degree[v]++;
- }
- if (check()) {
- printf("-1\n");
- return 0;
- }
- solve();
- printf("%I64d\n", ans);
- for (int i = 1; i <= n; i++) printf("%d", color[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3260453.html