阿里云服务器做网站好用吗,深圳微商城网站制作费用,深圳十大龙头企业,wap网站源码下载Graph
思路
图是联通的#xff0c;并且加边的时候要保证环一定是异或值为0#xff0c;所以我们可以保证从一个点到另一个点的路径异或值是不变的#xff0c;这个时候就简单了#xff0c;不就是一个异或最小生成树了嘛。
我们只要预处理一下#xff0c;任选一个点作为根…Graph
思路
图是联通的并且加边的时候要保证环一定是异或值为0所以我们可以保证从一个点到另一个点的路径异或值是不变的这个时候就简单了不就是一个异或最小生成树了嘛。
我们只要预处理一下任选一个点作为根节点去得到从这个点到其他点的路径异或值然后再做一遍异或最小生成树即可。
代码
/*Author : lifehappy
*/
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include bits/stdc.h#define mp make_pair
#define pb push_back
#define endl \nusing namespace std;typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int pii;const double pi acos(-1.0);
const double eps 1e-7;
const int inf 0x3f3f3f3f;inline ll read() {ll f 1, x 0;char c getchar();while(c 0 || c 9) {if(c -) f -1;c getchar();}while(c 0 c 9) {x (x 1) (x 3) (c ^ 48);c getchar();}return f * x;
}void print(ll x) {if(x 10) {putchar(x 48);return ;}print(x / 10);putchar(x % 10 48);
}const int N 1e5 10;int trie[N * 30][2], tot, a[N];int head[N], to[N 1], nex[N 1], value[N 1], cnt 1;void add(int x, int y, int w) {to[cnt] y;nex[cnt] head[x];value[cnt] w;head[x] cnt;
}void insert(int x) {int rt 0;for(int i 29; i 0; i--) {int now x i 1;if(!trie[rt][now]) {trie[rt][now] tot;rt trie[rt][now];trie[rt][0] trie[rt][1] 0;}else {rt trie[rt][now];}}
}int find(int x) {int ans 0, rt 0;for(int i 29; i 0; i--) {int now x i 1;if(trie[rt][now]) {rt trie[rt][now];}else {ans | 1 i;rt trie[rt][now ^ 1];}}return ans;
}ll ans 0;void dfs1(int l, int r, int dep) {if(dep 0 || l r) return ;int mid l - 1;while(mid r ((a[mid 1] dep) 1) 0) mid;dfs1(l, mid, dep - 1);dfs1(mid 1, r, dep - 1);if(mid l - 1 || mid r) return ;tot 0, trie[tot][1] trie[tot][0] 0;for(int i l; i mid; i) {insert(a[i]);}int now INT_MAX;for(int i mid 1; i r; i) {now min(now, find(a[i]));}ans now;
}void dfs2(int rt, int fa, int w) {a[rt] w;for(int i head[rt]; i; i nex[i]) {if(to[i] fa) continue;dfs2(to[i], rt, w ^ value[i]);}
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int n read();for(int i 1; i n; i) {int x read(), y read(), w read();add(x, y, w);add(y, x, w);}dfs2(1, 0, 0);sort(a, a n);dfs1(0, n - 1, 29);printf(%lld\n, ans);return 0;
}
