對(duì)于每個(gè)點(diǎn)都要答案

還是異或

trie樹合并石錘了

樸素枚舉是O(n^2*17)的

怎么辦呢？

?

我們發(fā)現(xiàn)合并的時(shí)候，一些部分的trie的子樹還是不變的

改變的部分也就是合并的復(fù)雜度可以接受

鑒于大部分trie都不變，而且是一個(gè)從上往下的過程，支持pushup維護(hù)

所以考慮dp，再在merge的pushup時(shí)候維護(hù)好dp值的更新

?

f[i]表示trie中以i為根子樹，最后的游戲結(jié)果

轉(zhuǎn)移分類討論：

如果x的sz==1，令dp[x]=-1

否則如果僅x的某一個(gè)子樹有sz，dp[x]=dp[son]

否則如果x的一個(gè)子樹sz==1，那么先手一定選擇這個(gè)子樹，一定更優(yōu)，那么后手的選擇就固定了，就是在另一個(gè)子樹trie上盡量使答案小。O(logn)轉(zhuǎn)移一下

否則，那么先手進(jìn)哪一個(gè)，后手一定跟進(jìn)去，所以兩個(gè)子樹的dp取max即可

?

復(fù)雜度：O(nlog^2n)不嚴(yán)格

#include<bits/stdc++.h> #define il inline #define reg register int #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){char ch;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x); } namespace Miracle{ const int N=100000+5; const int U=17;//sudhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh int a[N]; struct node{int nxt,to; }e[2*N]; int hd[N],cnt; int n; void add(int x,int y){e[++cnt].nxt=hd[x];e[cnt].to=y;hd[x]=cnt; } struct tr{int ls,rs;int sz,dp;int val; }t[N*40]; int tot; int calc(int x,int d,int s){int ret=0;int now=x;for(reg i=d+1;i<=U;++i){int c=(s>>(U-i))&1;if(c==1){if(t[now].ls) now=t[now].ls;else now=t[now].rs,ret+=(1<<(U-i));}else{if(t[now].rs) now=t[now].rs;else now=t[now].ls,ret+=(1<<(U-i));}}return ret; } void pushup(int x,int d){t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz;if(t[x].sz==1) t[x].val=t[t[x].ls].val+t[t[x].rs].val;if(t[x].sz==1){t[x].dp=-1;}if(!t[t[x].ls].sz){t[x].dp=t[t[x].rs].dp;}else if(!t[t[x].rs].sz){t[x].dp=t[t[x].ls].dp;}else{if(t[t[x].ls].sz==1){t[x].dp=calc(t[x].rs,d+1,t[t[x].ls].val)+(1<<(U-d-1));}else if(t[t[x].rs].sz==1){t[x].dp=calc(t[x].ls,d+1,t[t[x].rs].val)+(1<<(U-d-1));}else{t[x].dp=max(t[t[x].ls].dp,t[t[x].rs].dp);}} } void upda(int &x,int d,int v){if(!x) x=++tot;//cout<<" xx "<<x<<" d "<<d<<" v "<<v<<endl;if(d==U){++t[x].sz;t[x].val=v;if(t[x].sz==1){t[x].dp=-1;}else t[x].dp=0;return;}if(v&(1<<(U-d-1)))// cout<<"is 1",upda(t[x].ls,d+1,v);else //cout<<"is 0 ",upda(t[x].rs,d+1,v);pushup(x,d); } int merge(int x,int y,int d){if(!x||!y) return x+y;if(d==U){t[x].sz+=t[y].sz;t[x].dp=0;return x;}t[x].ls=merge(t[x].ls,t[y].ls,d+1);t[x].rs=merge(t[x].rs,t[y].rs,d+1);pushup(x,d);return x; } int rt[N]; int ans[N]; void dfs(int x,int fa){for(reg i=hd[x];i;i=e[i].nxt){int y=e[i].to;if(y==fa) continue;dfs(y,x);rt[x]=merge(rt[x],rt[y],0);}//cout<<" x "<<x<<" "<<rt[x]<<" : "<<t[rt[x]].dp<<" "<<t[rt[x]].sz<<endl;upda(rt[x],0,a[x]);ans[x]=t[rt[x]].dp; } int main(){rd(n);for(reg i=1;i<=n;++i)rd(a[i]);int x,y;for(reg i=1;i<n;++i){rd(x);rd(y);add(x,y);add(y,x);}dfs(1,0);for(reg i=1;i<=n;++i){printf("%d\n",ans[i]);}return 0; }} signed main(){freopen("3372.in","r",stdin);freopen("3372.out","w",stdout);Miracle::main();return 0; }/*Author: *Miracle*Date: 2019/2/3 17:19:49 */

總結(jié)：

考慮在變化中尋找不變的，再進(jìn)行維護(hù)

變化的畢竟在少數(shù)。

動(dòng)態(tài)點(diǎn)分治就是這個(gè)思想。

要大膽DP

再認(rèn)真分析維護(hù)的復(fù)雜度和方式。

?

也啟示我們線段樹不光是只能維護(hù)信息的存在與否。（其實(shí)都是靠pushup辣）

轉(zhuǎn)載于:https://www.cnblogs.com/Miracevin/p/10350816.html

總結(jié)

以上是生活随笔為你收集整理的fzyzojP3372 -- [校内训练20171124]博弈问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。