邢台移动网站建设价格,网络营销课程的心得体会,以前可以做视频的网站,百度搜索广告投放题目#xff1a; 题目背景 OURCE#xff1a;NOIP2015-SHY-7 题目描述 求一棵带边权的树的一条最大 Xor 路径的值。这里的“路径”不一定从根到叶子结点#xff0c;中间一段路径只要满足条件也可以。 输入格式 第一行#xff0c;一个整数 N #xff0c;表示一颗树有 N 个节… 题目 题目背景 OURCENOIP2015-SHY-7 题目描述 求一棵带边权的树的一条最大 Xor 路径的值。这里的“路径”不一定从根到叶子结点中间一段路径只要满足条件也可以。 输入格式 第一行一个整数 N 表示一颗树有 N 个节点接下来 N-1 行每行三个整数 a,b,c 表示节点 a 和节点 b 之间有条权值为 c 的边。 输出格式 输出仅一行即所求的最大值。 样例数据 1 输入 [复制] 4 1 2 3 1 3 4 1 4 7 输出 7 备注 【数据范围】对 40% 的输入数据 数据退化为一条链另对 10% 的输入数据 N≤1000对 100% 的输入数据 1≤N≤100000 c≤231-1。 题解 套路题 首先预处理出所有点到根节点的异或和XOR····然后将其转化成二进制从高位到低位储存到trie树上··容易想到两个点的XOR的异或和就是这两个点的路径的异或和····所以枚举每一个XOR,在trie树上走从高位开始查找与起位置上的数相反的数是否存在···如果存在优先选择···一边走一边计算答案即可 代码 #includecstdio
#includecstdlib
#includecmath
#includectime
#includecctype
#includestring
#includecstring
#includealgorithm
#includeiostream
using namespace std;
const int N1e55;
const int M4e65;
int fst[N],go[N*2],nxt[N*2],val[N*2],tot,n,xo[N],maxx,len;
struct node
{int son[2];
}tr[M];
inline int R()
{char c;int f0;for(cgetchar();c0||c9;cgetchar());for(;c9c0;cgetchar())f(f3)(f1)c-0;return f;
}
inline void comb(int a,int b,int v)
{nxt[tot]fst[a],fst[a]tot,go[tot]b,val[tot]v;nxt[tot]fst[b],fst[b]tot,go[tot]a,val[tot]v;
}
inline void dfs(int u,int fa)
{for(int efst[u];e;enxt[e]){int vgo[e];if(vfa) continue;xo[v]xo[u]^val[e];dfs(v,u);}
}
inline void insert(int x)
{int po0; for(int ilen-1;i0;i--){int temp(xi)1;if(!tr[po].son[temp]) tr[po].son[temp]tot;potr[po].son[temp];}
}
inline int check(int x)
{int ansx,po0;for(int ilen-1;i0;i--){int temp(xi)1;if(tr[po].son[temp^1]) ans|(1i),potr[po].son[temp^1];else ans^(tempi),potr[po].son[temp];}return ans;
}
int main()
{//freopen(a.in,r,stdin);nR();int a,b,c;for(int i1;in;i) {aR(),bR(),cR();maxxmax(maxx,c);comb(a,b,c);}dfs(1,0);int tempmaxx;while(temp) temp/2,len;tot0;for(int i2;in;i) insert(xo[i]); for(int i2;in;i)maxxmax(maxx,check(xo[i]));coutmaxxendl;return 0;
} 转载于:https://www.cnblogs.com/AseanA/p/7639894.html
