剪刀运送
30
p
t
s
30pts
30pts 树形
d
p
dp
dp 模板 然后题目不说树随机，游戏体验极差 考虑到树随机，那么暴力移重心不会移很长 重心一定是往加的链的中点移动 暴力移，移一步的
Δ
\Delta
Δ，考虑这条边的贡献 就是两边带权
s
i
z
e
size
size 的差 然后就是链加，子树求和 今天有点累，不想写了
送分题 考虑到操作次数
≤
2
e
4
\le 2e4
≤2e4，可以乱搞 先让颜色个数相同 然后交换两个点 因为交换两个点是很好写的
d
f
s
dfs
dfs 过去在退回来 考虑如何让颜色相同，暴力找到一个大于该有的颜色，一个小于该有的颜色，用小的染大的即可 然后发现一颗树可以完成上述所有操作 用操作次数简化码量 为了简化，我们要让一个点，找到另一个把颜色换给它，并且不能干扰已经确定的点 发现从叶子开始考虑，一个点被考虑当且仅当叶子被考虑完，并强制不往下走 发现从叶子开始考虑的这个限制正好对应
d
f
s
dfs
dfs 序 看来以后还是得学聪明一点
#include<bits/stdc++.h>
#define cs const
using namespace std
;
cs
int N
= 105, M
= N
* N
* 2;
int read(){
int cnt
= 0, f
= 1; char ch
= 0;
while(!isdigit(ch
)){ ch
= getchar(); if(ch
== '-') f
= -1;}
while(isdigit(ch
)) cnt
= cnt
* 10 + (ch
-'0'), ch
= getchar();
return cnt
* f
;
}
int col
[N
];
int goal
[N
];
int mp
[N
][N
];
int n
, m
, k
;
bool vis
[N
];
int ans
[M
][N
], len
;
int c1
[N
], c2
[N
], q
[N
], top
;
int num
[N
];
void dfs1(int u
){
c1
[col
[u
]]++; c2
[goal
[u
]]++;
q
[++top
] = u
; vis
[u
] = true;
for(int i
= 1; i
<= n
; i
++) if(mp
[u
][i
] && !vis
[i
]) dfs1(i
);
}
bool exi
[N
];
bool Find(int x
, int fa
, int goal
){
if(x
== goal
) return true; exi
[x
] = 1;
for(int i
= 1; i
<= n
; i
++){
if((i
^fa
) && mp
[x
][i
] && exi
[i
] == 0 && Find(i
, x
, goal
)){
++len
; memcpy(ans
[len
] + 1, ans
[len
- 1] + 1, sizeof(int)*n
);
if(!fa
) ans
[len
][x
] = ans
[len
][i
];
else swap(ans
[len
][x
], ans
[len
][i
]);
return true;
}
} return false;
}
bool Get(int x
, int goal
, int lim
){
if(x
== goal
) return true; exi
[x
] = true;
for(int i
= 1; i
<= n
; i
++){
if(mp
[x
][i
] && exi
[i
] == 0 && num
[i
] <= lim
&& Get(i
, goal
, lim
)){
++len
; memcpy(ans
[len
] + 1, ans
[len
- 1] + 1, sizeof(int)*n
);
swap(ans
[len
][x
], ans
[len
][i
]); return true;
}
} return false;
}
int main(){
n
= read(), m
= read(), k
= read();
for(int i
= 1; i
<= n
; i
++) col
[i
] = read();
for(int i
= 1; i
<= n
; i
++) goal
[i
] = read();
for(int i
= 1; i
<= m
; i
++){
int x
= read(), y
= read();
mp
[x
][y
] = mp
[y
][x
] = 1;
} memcpy(ans
[1] + 1, col
+ 1, sizeof(int)*n
);
len
= 1;
for(int i
= 1; i
<= n
; i
++){
if(!vis
[i
]){
memset(c1
, 0, sizeof(c1
));
memset(c2
, 0, sizeof(c2
));
top
= 0; dfs1(i
);
for(int j
= 0; j
< k
; j
++) if(c2
[j
] && !c1
[j
]){ puts("Impossible"); return 0; }
while(1){
bool ok
= 0;
for(int j
= 1; j
<= top
; j
++){
if(c1
[ans
[len
][q
[j
]]] > c2
[ans
[len
][q
[j
]]]){
ok
= 1;
for(int p
= 1; p
<= top
; p
++){
if(c1
[ans
[len
][q
[p
]]] < c2
[ans
[len
][q
[p
]]]){
memset(exi
, 0, sizeof(exi
));
c1
[ans
[len
][q
[j
]]]--; c1
[ans
[len
][q
[p
]]]++;
Find(q
[j
], 0, q
[p
]); break;
}
} break;
}
} if(!ok
) break;
}
for(int j
= 1; j
<= top
; j
++) num
[q
[j
]] = j
;
for(int j
= top
; j
; j
--){
if(ans
[len
][q
[j
]] != goal
[q
[j
]]){
for(int p
= 1; p
< j
; p
++){
if(ans
[len
][q
[p
]] == goal
[q
[j
]]){
memset(exi
, 0, sizeof(exi
));
Get(q
[j
], q
[p
], j
);
break;
}
}
}
}
}
}
for(int i
= 1; i
<= len
; i
++){
for(int j
= 1; j
<= n
; j
++) cout
<< ans
[i
][j
] << " ";
cout
<< '\n';
} return 0;
}
