https://open.kattis.com/problems/colourful
实际上用一棵树的边就行了，如果原树每种目标树有点颜色都有，那么就一定能行
那么把一棵树抠出来，然后某一种颜色少了，就随便找到一个点，然后再随便找一些比目标数多的颜色的点，一路交换到这个点旁边，然后把多的点变成这个少了的颜色
颜色数量一样后，再按照先序遍历的顺序，一个点一个点地安排，按先序遍历的目的是，已经搞好的子树就不用再移动他们了。
最多n个点颜色不一样，交换颜色数量最多n次，所以统一颜色数最多用10000次。然后一个点一个点地安排，每次最多交换n个点，那么也是最多用10000次，上限刚好200000次
代码格式有点难看，用emacs写的，交上去就成这样了。。
#include<bits/stdc++.h> using namespace std; const int maxl=110; int n,m,k,flag,ans,ansv; int a[maxl],ta[maxl],num[maxl],tnum[maxl]; int frm[maxl]; bool vis[maxl]; vector<int> e[maxl],ee[maxl],b; inline void predfs(int u) { vis[u]=true; for(int v:ee[u]) if(!vis[v]) { e[u].push_back(v); e[v].push_back(u); predfs(v); } b.push_back(u); } inline void prework() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]),num[a[i]]++; for(int i=1;i<=n;i++) scanf("%d",&ta[i]),tnum[ta[i]]++; int u,v; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); ee[u].push_back(v); ee[v].push_back(u); } predfs(1); } inline void print() { for(int i=1;i<=n;i++) printf("%d%c",a[i]," \n"[i==n]); } inline void dfs(int u) { vis[u]=true; if(num[a[u]]>tnum[a[u]]) { ansv=u; return; } for(int v:e[u]) if(!vis[v]) { frm[v]=u; dfs(v); if(ansv) return; } } inline void findcol(int u,int col) { vis[u]=true; if(a[u]!=ta[u] && a[u]==col) { ansv=u; return; } for(int v:e[u]) if(!vis[v]) { frm[v]=u; findcol(v,col); if(ansv) return; } } inline void mainwork() { ans=1; for(int i=0;i<k;i++) if(tnum[i]>0 && num[i]==0) ans=0; if(!ans) { puts("Impossible"); return; } print(); int u,v; for(int i=0;i<k;i++) if(num[i]<tnum[i]) { for(int j=1;j<=n;j++) if(a[j]==i) {u=j;break;} while(num[i]<tnum[i]) { for(int j=1;j<=n;j++) frm[j]=0,vis[j]=false; ansv=0; dfs(u);v=ansv; while(frm[v]!=u) { swap(a[v],a[frm[v]]); v=frm[v];print(); } num[a[v]]--;num[i]++; a[v]=i;print(); } } for(int d:b) if(a[d]!=ta[d]) { for(int i=1;i<=n;i++) frm[i]=0,vis[i]=false; ansv=0; findcol(d,ta[d]);v=ansv; while(v!=d) { swap(a[v],a[frm[v]]); v=frm[v];print(); } } } int main() { prework(); mainwork(); return 0; }
