题目大意:
给你一颗 n 个节点的边带权的树, 从树上求两点, 使得这两点的简单路径的边异或和最大.
数据输入:
多组数据, 每组数据的开始是 N(N<=100000), 接下来 N-1 行每行包括 3 个整数 u,v,w(0<=u,v<=n-1,0<=w<=231), 表示从 u 到 v 有一条长 w 的路径.
题解:
我们可以任意取一个根节点, 做一遍 dfs 求出任意节点到根节点的路径的异或和, 用数组 d 来表示. 那么对于任意两个节点 i 与 j, 它们之间路径的异或和就是 d[i]^d[j], 这是因为由于异或的特性, 它们之间的公共路径已经被异或掉了.
于是问题就转变成了, 求两点的最大异或和, 我们注意到题面中给的数据范围 (w<=231), 这提示我们把每一个点的 d 值拆成一串长 31 的 01 串, 并把没一个节点对应的 d 值插入 trie 树种, 因为要求最大, 我们从高位往低位插入, 当我们扫到一个点 $A_{i}$ 的值的时候, 我们基于贪心的思想尽量往与 $A_{i}$ 当前这一位相反的方向走, 只有当 trie 树中没有这相反的一位时, 我们才走相同的一位.
因为求 d 数组和插入, 查询都是 O(n) 的, 所以总时间复杂度是 O(n).
代码:
- #include
- #include
- #include
- using namespace std;
- typedef long long ll;
- const int N=100005;
- ll edge[2*N],d[N],ans;
- int ver[2*N],nxt[2*N],head[N];
- int trie[31*N][2];
- int n,tot=1,cnt;
- void add(int x,int y,ll z){ver[++cnt]=y,edge[cnt]=z,nxt[cnt]=head[x],head[x]=cnt;}
- void dfs(int x,int fa){
- for(int i=head[x];i;i=nxt[i]){
- int y=ver[i];
- if(y==fa) continue;
- d[y]=d[x]^edge[i];
- dfs(y,x);
- }
- }
- void insert(int x){
- ll k=d[x];
- int p=1;
- for(int i=30;i>=0;--i){
- int ch=(k>>i)&1;// 从高位往低位插入
- if(!trie[p][ch]) trie[p][ch]=++tot;
- p=trie[p][ch];
- }
- }
- ll search(int x){
- ll k=d[x],sum=0;
- int p=1;
- for(int i=30;i>=0;--i){
- int ch=(k>>i)&1;
- if(trie[p][!ch]){// 如果相反的一位存在
- sum+=pow((double)2,i);
- p=trie[p][!ch];
- }else p=trie[p][ch];// 不存在
- }
- return sum;
- }
- int main(){
- while(scanf("%d",&n)!=EOF){
- memset(trie,0,sizeof(trie));
- memset(head,0,sizeof(head));
- ans=0,cnt=0,tot=1;
- for(int i=1,u,v;i<n;++i){
- ll w;
- scanf("%d%d%lld",&u,&v,&w);
- add(u,v,w),add(v,u,w);
- }
- dfs(0,-1);// 求 d 数组
- for(int i=0;i<n;++i) insert(i);
- for(int i=0;i<n;++i) ans=max(ans,search(i));
- printf("%lld\n",ans);
- };
- return 0;
- }
[POJ3764] The XOR Longest Path 题解
来源: http://www.bubuko.com/infodetail-3254182.html