网站建设采取招标的方式,wordpress底部导航菜单,如何让网站火起来,腾讯官网首页登录入口P4551 最长异或路径
题意#xff1a;
给定一棵 n 个点的带权树#xff0c;结点下标从 1 开始到 n。寻找树中找两个结点#xff0c;求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
题解#xff1a;
我们指定1为根节点#xff0c;T(u,v…P4551 最长异或路径
题意
给定一棵 n 个点的带权树结点下标从 1 开始到 n。寻找树中找两个结点求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
题解
我们指定1为根节点T(u,v)表示u到v之间的路径的边权异或和那么T(u,v)T(root,u) Xor T(root,v) 所以我们可以将所有的T(root,u)插入到一个trie中对每个T(root,u)快速求出和它异或最大的T(root,v) 从trie的根开始如果能向和T(root,u)的当前位不同的子树走就向那边走否则没有选择
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn3e59;
int rtnum1;
struct tree_01{int cnt;int ch[2];void init(){ch[0]ch[1]0;cnt0;}
}tr[maxn4];
vectorpairint,int vec[maxn];
int ans0;
int dis[maxn];
void insert(int x){int rt1;for(int i30;i0;i--){int c((xi)1);if(tr[rt].ch[c]0){tr[rt].ch[c]rtnum;// tr[rtnum].init();}rttr[rt].ch[c];}
}
void get(int x){int rt1;int cnt0;for(int i30;i0;i--){int c((xi)1);if(tr[rt].ch[c^1]){rttr[rt].ch[c^1];cnt|(1i);}else if(tr[rt].ch[c])rttr[rt].ch[c];else break ;}ansmax(ans,cnt);
}
void dfs(int x,int fa){insert(dis[x]);get(dis[x]);for(auto it:vec[x]){int vit.first;int wit.second;if(vfa)continue;dis[v]dis[x]^w;dfs(v,x);}return ;
}
int main()
{int n;cinn;for(int i1;in;i){int u,v,w;cinuvw;vec[u].push_back({v,w});vec[v].push_back({u,w});}tr[1].init();dis[1]0;dfs(1,0);coutans;}
