相关链接
题目传送门:http://codeforces.com/contest/804/problem/C
解题报告
不难发现这货是个弦图
然后仔细想想,只要保证
在原图中,一个一个结点处理
所有处理过的结点组成一个连通块
就可以了
至于这样为什么是对的?
因为最小染色数很好确定,就是$\max(s_i)$
所以我们只需要求出染色方案数,所以只要染色随时是一个连通块就可以了
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 600009; int n,m,ans,head[N],to[N],nxt[N],sz[N],col[N]; vector<int> vis[N],lst[N]; set<int> que[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void AddEdge(int u, int v) { static int E = 1; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline void solve(int w, int f) { int cur = 1; for (int jj=0;jj<lst[w].size();jj++) { int j = lst[w][jj]; if (!col[j]) { while (!que[w].empty() && cur == *que[w].begin()) { ++cur; que[w].erase(que[w].begin()); } col[j] = cur; for (int k=0;k<vis[j].size();k++) { que[vis[j][k]].insert(cur); } } } for (int i=head[w];i;i=nxt[i]) { if (to[i] != f) { solve(to[i], w); } } } int main() { n = read(); m = read(); ans = 1; for (int i=1;i<=n;i++) { sz[i] = read(); ans = max(ans, sz[i]); for (int j=1,p;j<=sz[i];j++) { p = read(); vis[p].push_back(i); lst[i].push_back(p); } } for (int i=1;i<n;i++) { AddEdge(read(), read()); } solve(1, 1); cout<<ans<<endl; for (int i=1;i<=m;i++) { printf("%d ",col[i]? col[i]: 1); } return 0; }