题目 POJ3764 The xor-longest Path

[原题传送门](http://poj.org/problem?id=3764)

主要思路：

1.求出每个点到根节点（这里是树，所以直接取0）路径上所有权值xor和为d[i],则任意两点间路径xor和则为 d[x]^d[y]（至于证明，~~作者太懒，不想写~~）

2.接着用trie树跑出 max(d[x]^d[y]) (0<=x<n && 0<=y<n)

Code

#include<cstdio>

#include<cstring>

//#include<windows.h>

using namespace std;

#define rg register int

#define I inline int

#define V inline void

#define ll long long

#define db double

#define B inline bool

#define F1(i,a,b) for(rg i=a;i<=b;++i)

#define F2(i,a,b) for(rg i=a;i>=b;--i)

#define ed putchar('\n')

#define bl putchar(' ')

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

//char buf[1<<21],*p1=buf,*p2=buf;

const int N=100005;

template<typename TP>V read(TP &x)

{

	TP f=1;x=0;register char c=getchar();

	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;

	for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	x*=f;

}

template<typename TP>V print(TP x)

{

	if(x<0) x=-x,putchar('-');

	if(x>9) print(x/10);

	putchar(x%10+'0');

}

int n,a,b,c,ans,cnt=1,t[N<<5][2];

struct node{

	int v,w,nxt;

}e[N<<1];

int tot,h[N],d[N];

template<typename TP>V add(TP u,TP v,TP w)

{

	e[++tot].v=v;

	e[tot].w=w;

	e[tot].nxt=h[u];

	h[u]=tot;

}

template<typename TP>V dfs(TP x,TP fa)

{

//	print(d[x]),system("pause"),ed;

	for(TP i=h[x];i;i=e[i].nxt)

	{

		TP v=e[i].v,w=e[i].w;

		if(v==fa) continue;

		d[v]=d[x]^w;

		dfs(v,x);

	}

}

struct T{

	template<typename TP>V insert(TP val)

	{

		TP rt=1;

		F2(i,30,0)

		{

			TP id=val>>i&1;

			if(!t[rt][id]) t[rt][id]=++cnt;

			rt=t[rt][id];

		}

	}

	template<typename TP>I search(TP val)

	{

		TP rt=1,sum=0;

		F2(i,30,0)

		{

			TP id=val>>i&1;

			if(t[rt][id^1]) rt=t[rt][id^1],sum|=1<<i;

			else rt=t[rt][id];

		}

		return sum;

	}

}trie;

V init()

{

	ans=tot=0,cnt=1;

	memset(h,0,sizeof h);

	memset(t,0,sizeof t);

}

int main()

{

	while(~scanf("%d",&n))

	{

		init();

		F1(i,1,n-1)

		{

			read(a),read(b),read(c);

			add(a,b,c),add(b,a,c);

		}

		d[0]=0,dfs(0,-1);

		F1(i,0,n-1)

		{

			trie.insert(d[i]);

			ans=Max(ans,trie.search(d[i]));

		}

		print(ans),ed;

//		F1(i,0,n-1) print(d[i]),bl;

	}

	return 0;

}

巴特西

POJ3764

题目 POJ3764 The xor-longest Path

主要思路：

Code

最新文章

热门文章