@spoj - COT3@ Combat on a tree

野性酷女 2023-06-01 13:56 23阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

Alice 和 Bob 在一棵 n 个节点的树上玩游戏，每个节点初始要么为黑色要么为白色。

Alice 先手，轮流进行如下操作：  
选择一个白色点 v，将路径 (1, v) 全部染成黑色。  
最后不能操作的人为输。

帮忙计算 Alice 是否必胜以及所有必胜可能的第一步结点的选择。

**Input**  
第一行给出 n，表示结点数量，1<=n<=100000。  
第二行包含 n 个整数 c1,c2,..cn，0<=ci<=1，描述每个结点的颜色。其中 0 为白 1 为黑。  
接下来 n-1 行描述树上的 n-1 条边，每行包含两个整数 u, v。

**Output**  
如果必败，输出 -1。  
否则，按升序输出所有可能的第一步选择。

**Example**  
**Input\#1:**  
8  
1 1 0 1 0 0 1 0  
1 2  
1 3  
2 6  
3 4  
3 5  
5 7  
7 8  
**Output\#1:**  
5  
**Input\#2:**  
20  
1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0  
1 2  
2 3  
2 4  
1 5  
1 6  
5 7  
5 8  
2 9  
8 10  
1 11  
1 12  
9 13  
6 14  
14 15  
7 16  
11 17  
2 18  
7 19  
12 20  
**Output\#2**  
8  
11  
12

## @solution@ ##

考虑第一步删去一条路径 (1, v)，实际上得到了若干不相交的子树（森林），即若干游戏的组合。  
所以我们可以使用 sg 函数递推求解这道题。

求解 sg\[x\] 时，朴素做法是枚举 x 这棵子树内的某个白点 i，统计删去 (x, i) 这条路径后剩下的森林 sg 的异或和，再对所有 i 做完后求 mex。  
可以发现这个做法是 O(n^2) 的，考虑优化。

考虑从 x 递推到它的父亲时，实际上是把 x 子树内所有链都伸长了一点，然后异或上伸长过后新产生的枝末的 sg。  
考虑可以使用一个结构维护 x 子树内所有的可行链，支持整体异或与合并，以及求解 mex。

启发式合并当然是很好的，但是这个模型可以使用线段树合并做到更优秀的复杂度。  
然而线段树合并不大好支持整体异或的同时求解 mex。然而异或这种东西可以使用 01 trie 搞定。  
考虑可以类比线段树合并的过程，使用 trie 来进行合并，总时间复杂度可以做到 O(n\*logn)。

trie 怎么打异或 tag 呢？可以将异或的数直接存储，下传时直接异或到儿子的 tag 上去。如果第 i 层的 tag 二进制下为 1 则交换左右子树。  
至于求 mex，可以存储一个 cover 表示这个区间是否所有数都存在，做个类线段树二分即可。

最后 dfs 一下就能算出以每个点为第一步过后局面的值，挑出其中为 0 的即是必胜策略。

## @accepted code@ ##

#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 100000; struct edge{ edge *nxt; int to; }edges[2*MAXN + 5], *adj[MAXN + 5], *ecnt; void addedge(int u, int v) { edge *p = (++ecnt); p->to = v, p->nxt = adj[u], adj[u] = p; p = (++ecnt); p->to = u, p->nxt = adj[v], adj[v] = p; } struct node{ node *ch[2]; int tag; bool flag; }pl[40*MAXN + 5], *rt[MAXN + 5], *ncnt, *NIL; void init() { ecnt = &edges[0], ncnt = NIL = &pl[0]; NIL->ch[0] = NIL->ch[1] = NIL; } node *new_trie(int k, int dep) { node *p = (++ncnt); p->ch[0] = p->ch[1] = NIL; p->tag = 0; if( dep == -1 ) { p->flag = true; return p; } if( (k >> dep) & 1 ) p->ch[1] = new_trie(k, dep - 1); else p->ch[0] = new_trie(k, dep - 1); return p; } void pushdown(node *rt, int dep) { if( rt->tag ) { if( (rt->tag >> dep) & 1 ) swap(rt->ch[0], rt->ch[1]); if( rt->ch[0] != NIL ) rt->ch[0]->tag ^= rt->tag; if( rt->ch[1] != NIL ) rt->ch[1]->tag ^= rt->tag; rt->tag = 0; } } void pushup(node *rt) { if( rt->ch[0]->flag && rt->ch[1]->flag ) rt->flag = true; } node *merge(node *rt1, node *rt2, int dep) { if( rt1 == NIL ) return rt2; if( rt2 == NIL ) return rt1; if( dep == -1 ) return rt1; pushdown(rt1, dep), pushdown(rt2, dep); rt1->ch[0] = merge(rt1->ch[0], rt2->ch[0], dep - 1); rt1->ch[1] = merge(rt1->ch[1], rt2->ch[1], dep - 1); pushup(rt1); return rt1; } int search_mex(node *rt, int dep) { if( dep == -1 ) return 0; pushdown(rt, dep); if( rt->ch[0]->flag ) return search_mex(rt->ch[1], dep - 1) | (1<<dep); else return search_mex(rt->ch[0], dep - 1); } int c[MAXN + 5]; int sg[MAXN + 5], sum[MAXN + 5]; void dfs1(int x, int f) { for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs1(p->to, x); sum[x] ^= sg[p->to]; } rt[x] = (c[x] ? NIL : new_trie(sum[x], 18)); for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; rt[p->to]->tag ^= (sum[x] ^ sg[p->to]); rt[x] = merge(rt[x], rt[p->to], 18); } sg[x] = search_mex(rt[x], 18); //printf("! %d %d\n", x, sg[x]); } vector<int>ans; void dfs2(int x, int f, int k) { k ^= sum[x]; if( k == 0 && c[x] == 0 ) ans.push_back(x); for(edge *p=adj[x];p;p=p->nxt) { if( p->to == f ) continue; dfs2(p->to, x, k^sg[p->to]); } } int main() { init(); int n; scanf("%d", &n); for(int i=1;i<=n;i++) scanf("%d", &c[i]); for(int i=1;i<n;i++) { int u, v; scanf("%d%d", &u, &v); addedge(u, v); } dfs1(1, 0); if( !sg[1] ) puts("-1"); else { dfs2(1, 0, 0); sort(ans.begin(), ans.end()); for(int i=0;i<ans.size();i++) printf("%d\n", ans[i]); } }

## @details@ ##

注意必须选择白点才能合法。任何时候（求 sg 函数值或求合法第一步）都不能考虑黑点的贡献。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11330421.html