AT2675 [AGC018F] Two Trees

首先我們看到1或-1，那么就是限制差距在1以內，然后我們可以想到構造一些東西來滿足這種東西，然后我們經常利用的就是歐拉回路。
首先這是兩個樹，然后我們可以根據兒子個數來判斷當前點的奇偶性，如果相同編號在兩個樹上奇偶性不同，那么必然無解，否則我們一定能夠構造一組解。具體方法就是讓偶點賦值為0，然后考慮兩個樹上相同編號奇點連邊，這時候就滿足所有點的度數都是偶數的限制了，但是對于根需要處理一下，建一個虛擬根連接兩個樹根，那么這樣跑出來歐拉回路，根據方向來確定賦值1或-1。
我們發現對于任意一個點的子樹總的只會是進一條邊或出去一條邊，因為從父親只進來或出去一條邊。這樣我們就滿足了題目要求的限制。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的AT2675 [AGC018F] Two Trees(欧拉回路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。