| 题目名称 | 3474. [POJ 3764] 最长异或路径 |
|---|---|
| 输入输出 | xorlongestpath.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2020-09-14加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：15， 提交：38， 通过率：39.47% | ||||
 ┭┮﹏┭┮ |
100 | 0.101 s | 5.42 MiB | C++ |
|
syzhaoss |
100 | 0.109 s | 1.81 MiB | C++ |
 数声风笛ovo |
100 | 0.126 s | 5.94 MiB | C++ |
 cb |
100 | 0.152 s | 34.97 MiB | C++ |
|
yrtiop |
100 | 0.168 s | 1.31 MiB | C++ |
|
struggle |
100 | 0.193 s | 7.46 MiB | C++ |
|
郑霁桓 |
100 | 0.205 s | 7.77 MiB | C++ |
|
小金 |
100 | 0.208 s | 6.79 MiB | C++ |
|
超人 |
100 | 0.210 s | 18.69 MiB | C++ |
 ShallowDream雨梨 |
100 | 0.212 s | 13.41 MiB | C++ |
| 关于 最长异或路径 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
真·神の思路
| ||||
3474. [POJ 3764] 最长异或路径
★★☆ 输入文件：xorlongestpath.in
输出文件：xorlongestpath.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
给定一个有 $n$ 个顶点的树，树上的边都具有权值。
树中一条路径的异或长度被定义为路径上所有边的权值的异或。
那么树中所有顶点之间路径的异或长度的结果最大是多少？
【输入格式】
第一行包含整数 $n$，表示树的顶点数目。
接下来 $n-1$ 行，每行包括三个整数 $x,y,w$，表示顶点 $x$ 和顶点 $y$ 之间有一条边权重为 $w$。
【输出格式】
输出一个整数，表示最大的异或长度。
【样例输入】
4 0 1 3 1 2 4 1 3 6
【样例输出】
7
【数据范围】
对于 $50\%$ 的数据，$1\leq n\leq 100$;
对于 $100\%$ 的数据，$1\leq n\leq 10^5,0\leq x,y<n,0\leq w<2^{31}$;
【来源】
《算法竞赛进阶指南》