求个网站2020急急急,网站定位模板,物联网平台层,Wordpress 核心思想题目
n(n2e5)个点的树#xff0c;点i权值ai#xff08;1ai2^30#xff09;
修改最少的点的权值#xff0c;使得树上不存在异或和为0的简单路径#xff0c;输出最少的点数
权值可以被修改成任意正整数#xff08;可以是无限大#xff09;
思路来源
官方…题目
n(n2e5)个点的树点i权值ai1ai2^30
修改最少的点的权值使得树上不存在异或和为0的简单路径输出最少的点数
权值可以被修改成任意正整数可以是无限大
思路来源
官方题解 zlt题解 题解
假设树形是固定的dfs往上回溯的时候
如果一条路径xor为0这条路径上必须改一个值
贪心地来看lca必须要改
由于可以改成任意值改lca视为把这棵子树断掉
XOR(u,v) XOR(根到u) xor XOR(根到v) xor a[lca(u,v)]
那就是判一下某个点的子树是否存在两个点的祖先异或等于本身的权值
这个可以启发式合并的时候把小的集合往大的集合上挂的时候判断
删除某个点就可以认为是清空集合
心得
自己的写法怎么写都写不对都wa8感觉是启发式合并公有map导致的
只能抄官方题解每个节点维护一个set了
代码
#includeiostream
#includecstdio
#includeunordered_map
#includeset
#includebits/stdc.h
using namespace std;
typedef long long ll;
typedef pairint,ll P;
#define fi first
#define se second
#define pb push_back
const int N2e510,INF0x3f3f3f3f,mod1e97;//998244353
int n,x,y,ans;
setintnow[N];
int a[N],sz[N];
bool ban[N];
vectorintE[N];
void dfs(int u,int fa,int w){bool ban0;now[u].insert(w);for(auto v:E[u]){if(vfa)continue;dfs(v,u,w^a[v]);if(now[u].size()now[v].size())now[u].swap(now[v]);for(auto x:now[v]){if(now[u].count(x^a[u])){ban1;break;}}for(auto x:now[v]){now[u].insert(x);}now[v].clear();}if(ban){now[u].clear();ans;}
}
int main(){scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);}for(int i2;in;i){scanf(%d%d,x,y);E[x].push_back(y);//E[i].pb(P(fa,w));E[y].push_back(x);//E[i].pb(P(fa,w));}dfs(1,0,a[1]);printf(%d\n,ans);return 0;
}
