[SPOJ COT3]COT3 - Combat on a tree

題目連結

如果要看懂這個題解，請先了解組合賽局的$SG$函數和$Nim$和的性質

這題的盤面感覺很複雜
不妨先假設所有點都是白色的吧

還是好複雜？
不妨先從一個點來討論吧

一個點的$SG\ value$當然就是$1$囉

然後拓展到兩個點
$SG\ value$變成$2$了

拓展到三個點
如果三個點成鏈狀，$SG\ value$當然就是$3$了
如果是櫻桃形的，$SG\ value$可以照以下方式算出 ($\oplus$是$XOR$的符號)

可以得到$SG\ value=mex\{0,1,1\}=2$

一般的，我們可以用以下方式來算出以任何一個點為根的子樹的$SG\ value$ (注意這裡假設每個點都是白色的)

(之後將通通以這張圖做參考)
注意到選了$4$這個節點之後，整棵樹分裂成了$4$個子遊戲
選了$4$之後整個盤面的$SG\ value$就是這些子遊戲的$SG\ value$的$Nim$和 ($\oplus$)
我們只要枚舉$11$種選擇，就可以算出這個盤面的$SG\ value$
也就是$mex\{選了i之後整個盤面的SG\ value,1\leq i\leq 11\}$

利用記憶化搜索，再加上一些避免重複計算的小技巧，可以做到時間複雜度$O(N^{2})$
很可惜的，這樣當然還不夠好

說明：
子樹$u$為以$u$為根的子樹
$SG(xxx)$為盤面為$xxx$的$SG\ value$

如果現在要算$SG(子樹1)$，而且正在枚舉子樹$4$的點
可以發現，$SG(子樹1選擇8後的盤面)=SG(子樹4選擇8後的盤面)\oplus SG(子樹3)\oplus SG(子樹2)$
因為正在枚舉子樹$4$的點，所以$SG(子樹3)\oplus SG(子樹2)$可以視為常數！

這樣，如果我們用某種資料結構存下計算$SG(子樹4)$時的中間結果 (也就是$SG(子樹4選擇u後的盤面)$)
如果這個資料結構支持在短時間內
1. 將全部資料$\oplus$一個數字
2. 算出全部資料的$mex$
3. 插入一個數字

再套用啟發式合併，就解決了
$copy-on-write$的二元$trie$，搭配懶惰標記，剛好符合所有需求！
實作上並不是那麼的困難，就不細講了
提示：把每個數字轉換成二進位，然後當作$01$字串來看
另外，我的啟發式合併有點隱形，請參考函數Node *Merge(Node *a,Node *b,const int depth)

這樣就做完了嗎？
好像還沒耶

我們假設每個點都是白色的
現在有些點可能是黑色的

其實......仔細想想，那些黑色的點直接忽略就好了
具體實現要用什麼樣的方式忽略
請參考下面的code吧

你認為這份code就可以拿去AC了嗎？
好像還沒耶哈哈
這份code常數過大會導致TLE，優化的方法和code在這裡

時間複雜度：$O(N\log^2N)$

code:

#include<cstdio>
//#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
void assert(bool valid){if(valid)return;for(;;)putchar('E');}
struct Node
{
    Node *ch[2];
    int sum,tag;
    vector<int>*ids;
    Node():ch{NULL,NULL},sum(0),tag(0),ids(new vector<int>()){}
};
void PutDown(Node *o,const int depth)
{
    if((1<<depth)&o->tag)swap(o->ch[0],o->ch[1]);
    for(int d=0;d<2;d++)if(o->ch[d])o->ch[d]->tag^=o->tag;
    o->tag=0;
}
int Sum(Node *o){return o?o->sum:0;}
void Maintain(Node *o)
{
    o->sum=Sum(o->ch[0])+Sum(o->ch[1]);
}
void Insert(Node* &o,const int depth,const int value,const int id)
{
    if(!o)o=new Node();
    if(depth==-1){o->sum=1,o->ids->push_back(id);return;}
    PutDown(o,depth);
    Insert((o->ch[(1<<depth)&value)>>depth],depth-1,value,id);//note the priority of bitwise operators
    Maintain(o);
}
vector<int>*Merge(vector<int>*a,vector<int>*b)
{
    if(a->size()<b->size())swap(a,b);
    for(const int v:*b)a->push_back(v);
    return a;
}
Node *Merge(Node *a,Node *b,const int depth)
{
    if(!a||!b)return a?a:b;
    Node *ans=new Node();
    if(depth==-1)ans->sum=(a->sum)|(b->sum),ans->ids=Merge(a->ids,b->ids);
    else
    {
        PutDown(a,depth),PutDown(b,depth);
        ans->ch[0]=Merge(a->ch[0],b->ch[0],depth-1);
        ans->ch[1]=Merge(a->ch[1],b->ch[1],depth-1);
        Maintain(ans);
    }
    return ans;
}
int GetSG(Node *o,const int depth,const int now)
{
    if(!o||depth==-1)return now;
    PutDown(o,depth);
    if(Sum(o->ch[0])<(1<<depth))return GetSG(o->ch[0],depth-1,now);
    else
    {
        assert(Sum(o->ch[1])<(1<<depth));
        return GetSG(o->ch[1],depth-1,now+(1<<depth));
    }
}
int N,COLOR[100000];
vector<int>ET[100000];
Node *GetTree(const int u,const int parent,int &allsg)
{
    vector<Node*>ch_trees;
    vector<int>ch_sgs;
    allsg=0;
    for(const int nxt:ET[u])if(nxt!=parent)
    {
        int ch_sg;
        ch_trees.push_back(GetTree(nxt,u,ch_sg));
        ch_sgs.push_back(ch_sg);
        allsg^=ch_sg;
    }
    Node *ans=NULL;
    for(int i=0;i<(int)ch_trees.size();i++)if(ch_trees[i])
    {
        ch_trees[i]->tag^=allsg^ch_sgs[i];
        ans=Merge(ans,ch_trees[i],30);
    }
    if(COLOR[u]==0)Insert(ans,30,allsg,u),allsg=GetSG(ans,30,0);
    return ans;
}
vector<int>*GetIds(Node *o)
{
    for(int depth=30;depth>=0;depth--)
    {
        PutDown(o,depth);
        o=o->ch[0],assert(o);
    }
    return o->ids;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d",&N)==1)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=0;i<N;i++)scanf("%d",&COLOR[i]);
        for(int i=0,a,b;i<N-1;i++)
        {
            scanf("%d%d",&a,&b),a--,b--;
            ET[a].push_back(b),ET[b].push_back(a);
        }
        int ans;
        Node *o=GetTree(0,-1,ans);
        ans=GetSG(o,30,0);
        if(ans==0)puts("-1");
        else
        {
            assert(o);
            vector<int>*ans=GetIds(o);
            sort(ans->begin(),ans->end());
            for(const int v:*ans)printf("%d\n",v+1);
        }
    }
    return 0;
}