丽水 网站建设,wordpress链接 数据库文件,建立网站的必要性,施工员证书查询网站正题
POJ题目链接:http://poj.org/problem?id3764 其实loj也有题目:https://loj.ac/problem/10056 题目大意
一棵树#xff0c;求两个点使他们的之间的边的异或值最大。 解题思路
我们可以先算出所以点离根的路上的边的异或值#xff0c;记为didi#xff0c;然后根据异…正题
POJ题目链接:http://poj.org/problem?id3764 其实loj也有题目:https://loj.ac/problem/10056 题目大意
一棵树求两个点使他们的之间的边的异或值最大。 解题思路
我们可以先算出所以点离根的路上的边的异或值记为didid_i然后根据异或值的尿性两个点重复的路上就会被相互异或抵消掉所以两个点之间的距离就是di⊕djdi⊕djd_i\oplus d_j然后就和loj#10050-The XOR Largest Pair【Trie(字典树)】一样了。 code
#includecstdio
#includealgorithm
#includecstring
#define N 100010
using namespace std;
int n,l[N*40][2],x,tot,a[N],ls[N],num,y,w;
int maxs;
struct line{int to,next,w;
}edge[N*2];
void addl(int x,int y,int w)//加边
{edge[num].toy;edge[num].ww;edge[num].nextls[x];ls[x]num;
}
void dfs(int x)//深搜求距离
{for(int ils[x];i;iedge[i].next){int yedge[i].to;if(a[y]!-1) continue;a[y]a[x]^edge[i].w;dfs(y);}
}
int main()
{while(~scanf(%d,n)){memset(a,-1,sizeof(a));memset(l,0,sizeof(l));memset(ls,0,sizeof(ls));tot0;num0;maxs0;for(int i1;in;i){scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}a[1]0;dfs(1);for(int i1;in;i){int now0;for(int j30;j0;j--){x(a[i]j)1;if(!l[now][x]) l[now][x]tot;nowl[now][x];}}for(int i1;in;i){int now0;int ans0;for(int j30;j0;j--){x((a[i]j)1)^1;if(!l[now][x]) nowl[now][x^1];else{ans1j;nowl[now][x];}}maxsmax(maxs,ans);}printf(%d\n,maxs);}
}
