Codeforces Round #835 (Div. 4) G. SlavicG‘s Favorite Problem

news/2024/4/22 17:23:08/

翻译:

给您一个带有𝑛顶点的加权树。回想一下,树是一个没有任何循环的连通图。加权树是每条边都有一定权重的树。树是无向的,它没有根。

因为树木让你厌烦,所以你决定挑战自己,在给定的树上玩一款游戏。

在移动中,您可以从一个节点移动到它的一个邻居(与它有直接边的另一个节点)。

你从一个变量𝑥开始,它最初等于0。当您通过边缘𝑖时,𝑥将其值更改为𝑥𝖷𝖮𝖱𝑤𝑖(其中𝑤𝑖是𝑖-th边缘的权重)。

您的任务是从顶点𝑎到顶点𝑏,但是当且仅当到达节点𝑏后,𝑥的值将变为0时,允许您进入节点𝑏。换句话说,您只能通过使用边缘𝑖来访问节点𝑏,这样𝑥𝖷𝖮𝖱𝑤𝑖=0。一旦你进入节点𝑏,游戏就结束了,你就赢了。

此外,你最多可以在任何时间点传送一次到除顶点𝑏外的任何顶点。你可以从任何顶点传送,甚至从𝑎。

如果你能从𝑎到达顶点𝑏,回答“YES”,否则回答“NO”。

注意,𝖷𝖮𝖱表示按位异或操作。

输入
第一行包含一个整数𝑡(1≤𝑡≤1000)——测试用例的数量。

每个测试用例的第一行分别包含三个整数𝑛、𝑎和𝑏(2≤𝑛≤105),(1≤𝑎,𝑏≤𝑛;𝑎≠𝑏)——顶点的数量,以及起始节点和期望的结束节点。

接下来的每一行𝑛−1表示树的一条边。边缘𝑖用三个整数𝑢𝑖,𝑣𝑖和𝑤𝑖——顶点连接的标签(1≤𝑢𝑖,𝑣𝑖≤𝑛;𝑢𝑖≠𝑣𝑖;1≤𝑤𝑖≤109)的重量和各自的优势。

可以保证所有测试用例中𝑛的总和不超过105。

输出
对于每个测试用例,如果你能到达顶点𝑏,输出“YES”,否则输出“NO”。

例子
inputCopy
3.
5 1 4
1 3 1
2 3 2
4 3 3
3 5 1
2 1 2
1 2 2
6 2 3
1 2 1
2 3 1
3 4 1
4 5 3
5 6 5
outputCopy
是的
没有
是的
请注意
对于第一个测试用例,我们可以从节点1移动到节点3,𝑥从0变为1,然后我们从节点3移动到节点2,𝑥变为等于3。现在,我们可以传送到节点3,并从节点3移动到节点4,到达节点𝑏,因为𝑥最终变成了0,所以我们应该回答“YES”。

对于第二个测试用例,我们没有移动,因为我们不能传送到节点𝑏,我们唯一的移动是移动到节点2,这是不可能的,因为𝑥到达节点2时不等于0,所以我们应该回答“no”。

思路:

无向图,a到达b路径上一直异或,到最后到达为0,中间可以传送到任何一个地点。那么我们只需要跑两个dfs,然后看知道到相互的点是否直接为0,或者有点有相同的值即可。

代码:

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stdio.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<numeric>
#include<stack>
using namespace::std;
typedef long long  ll;
int n,t;
inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;
}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9)print(x / 10);putchar(x % 10 + '0');
}int a,b;
int x,y,z;
map<ll,int>we;
ll dd[100005];
int jjk=0;
set<ll>wee;
vector<pair<int,int>>q[100005];
void dfs(int x,int fa){if (x==b) {if (dd[x]==0) {jjk=1;}return;}for (int i =0; i<q[x].size(); i++) {if (q[x][i].first==fa) {continue;}dd[q[x][i].first]=dd[x]^q[x][i].second;if (q[x][i].first!=b) {we[dd[q[x][i].first]]=1;}dfs(q[x][i].first, x);}
}
void dfs2(int x,int fa){if (we[dd[x]]&&x!=b) {
//            printf("%d \n",x);
//            printf("dsa\n");jjk=1;}
//    if (dd[x]==0) {
//                jjk=1;
//        }for (int i =0; i<q[x].size(); i++) {if (q[x][i].first==fa) {continue;}dd[q[x][i].first]=dd[x]^q[x][i].second;dfs2(q[x][i].first, x);}
}
void solv(){we.clear();jjk=0;cin>>n>>a>>b;for (int i =0; i<=n; i++) {q[i].clear();}for (int i =1; i<n; i++) {cin>>x>>y>>z;q[x].push_back({y,z});q[y].push_back({x,z});}
//    if (n==2) {
//        printf("NO\n");return;
//    }
//        for (int i =1; i<=n; i++) {
//            dd[i]=0;
//        }
//dd[a]=0;dfs(a,a);
//    for (int i =1; i<=n; i++) {
//        printf("%lld ",dd[i]);
//    }printf("\n");
//    for (int i =1; i<=n; i++) {
//        dd[i]=0;
//    }dd[b]=0;we[0]=1;dfs2(b, b);
//    for (int i =1; i<=n; i++) {
//        printf("%lld ",dd[i]);
//    }printf("\n");if (jjk) {printf("YES\n");return;}printf("NO\n");
//    4
//    4 3 2
//    3 1 1
//    1 4 1
//    1 2 3
}
int main(){ios::sync_with_stdio(false);cin.tie(); cout.tie();cin>>t;while (t--) {solv();}return 0;
}

 


http://www.ppmy.cn/news/300051.html

相关文章

Codeforces Round #835(div4) A~G题解

前言 也是好久没有打div4了&#xff0c;上一次还是半年前的第二场cf比赛&#xff0c;记得当时过了3题&#xff0c;非常开心。这一次过了5个题&#xff0c;D题调试时间太久&#xff0c;导致F题最后没时间调试了。总之还不错。 Codeforces Round #835(div4)补题链接 A. Medium …

Codeforces Round #835 (Div. 4) A~F题解

原题地址&#xff1a;Codeforces Round #835 (Div. 4) 题目&#xff1a;A. Medium Number 题意&#xff1a; 没什么好说的&#xff0c;输出中间那个数即可 代码&#xff1a; #include<bits/stdc.h> #include<iostream> #include<algorithm> #include<…

【Codeforces Round #835 (Div. 4)】A——G题解

文章目录 A Medium Number题意思路代码 B Atillas Favorite Problem题意思路代码 C Advantage题意思路代码 D Challenging Valleys题意思路代码 E Binary Inversions题意思路代码 F Quests题意思路代码 G SlavicGs Favorite Problem题意思路代码 A Medium Number 题意 三个数…

微信 iPad 835协议

微信 iPad 协议是指用于在 iPad 设备上使用微信应用的技术协议。一般来说&#xff0c;通过该协议可以将微信账号同步到 iPad 设备上&#xff0c;并且可以在 iPad 上发送和接收微信消息&#xff0c;查看好友列表、聊天记录等功能。微信 iPad 协议是通过私有API实现的。 需要一定…

大厂设计师都在用的9个灵感工具

每一件伟大的设计作品都离不开设计师灵感的爆发。设计师有很多灵感来源&#xff0c;比如精美的摄影图片、酷炫的网站设计、APP的特色功能、友好的用户体验动画&#xff0c;或者一篇文章。 设计师每天都需要收集灵感&#xff0c;把灵感收集当成日常生活。在这篇文章中&#xff…

高通 Msm835平台充电功能的开发与调试

目录 平台充电相关代码&#xff1a; 835平台kernel充电相关代码&#xff1a; 关机充电的系统相关代码&#xff1a; 835平台UEFI 充电相关代码&#xff1a; 835平台电池曲线&#xff1a; 电池曲线大体内容如下: kernel 电池曲线的提交&#xff1a; XBL 关于充电曲线的提…

23年海南大学835上岸考研资料(历年真题)及笔记(耗时1年)

23年&#xff0c;海南大学835软件工程上岸必备资料&#xff08;历年真题&#xff09;及笔记&#xff08;耗时一年&#xff09;&#xff01; 首先挂一下22年考试qun图&#xff0c;qun里给大家每日分享考研英语和数学&#xff0c;专业课等&#xff0c;全程给大家解决考研路上的疑…

【P56】JMeter 响应时间图(Response Time Graph)

文章目录 一、响应时间图&#xff08;Response Time Graph&#xff09;参数说明二、准备工作三、测试计划设计 一、响应时间图&#xff08;Response Time Graph&#xff09;参数说明 可以以图形的方式查看和分析各事务和取样器的响应时间 使用场景&#xff1a;用于评估测试结…

【计算机网络复习之路】运输层(谢希仁第八版)万字详解 主打基础

运输层是OSI七层模型中最重要最关键的一层&#xff0c;是唯一负责总体数据传输和控制的一层。运输层要达到两个主要目的&#xff1a;第一&#xff0c;提供可靠的端到端的通信&#xff08;“端到端的通信” 是应用进程之间的通信&#xff09;&#xff1b;第二&#xff0c;向会话…

代码随想录算法训练营第四十九天|股票问题专题(1)

目录 LeeCode 121. 买卖股票的最佳时机 LeeCode 122.买卖股票的最佳时机II LeeCode 121. 买卖股票的最佳时机 121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 动归五部曲&#xff1a; 1.确定dp数组及下标含义: dp[i][0] 表示第i天持有股票所得最多现金;…

详解Java异常和异常面试题(上)

1.异常的体系结构 2.从程序执行过程&#xff0c;看编译时异常和运行时异常 编译时异常&#xff1a;执行javac.exe命名时&#xff0c;可能出现的异常 运行时异常&#xff1a;执行java.exe命名时&#xff0c;出现的异常 1.运行时异常  是指编译器不要求强制处置的异常。一般是…

KL15上电

今天测试了一下单板的上电过程&#xff0c;发现了一个很神奇的现象&#xff1a;如果先是KL15掉电&#xff0c;然后KL30掉电&#xff0c;那么重新上KL30时单板没有任何反应&#xff1b;如果直接KL30掉电&#xff0c;那么重新上KL30时&#xff0c;会先有电流然后掉电。 研究后发…

联想笔记本K4350安装win7系统

【阅读文章申明】 作者只是想把自己实践中的经验分享给大家&#xff0c;如果文章里面有在大神面前显的很低级的知识点。那么大神你可以不看&#xff0c;请不要发一些“浪费流量”“辣鸡”之类嘲讽的话&#xff0c;每一篇文章都是作者自己。截图&#xff0c;编辑&#xff0c;排版…

Mellanox 5 RDMA网卡驱动安装

RDMA网卡驱动安装 1. RDMA驱动安装2. RDMA网卡实验与带宽测试 1. RDMA驱动安装 # 1. get OFED # https://cn.mellanox.com/products/infiniband-drivers/linux/mlnx_ofedtar -xvf xxx.tar.gzcd MLNX_OFED_LINUX-xxxx-x86_64sudo ./mlnxofedinstall --add-kernel-support# afte…

nuc977 添加EC20 4G 网卡

参考了手册和网上的文章。做下记录。 内核版本&#xff1a;linux-3.10 1. Add VID and PID 在/drivers/usb/serial/option.c添加: static const struct usb_device_id option_ids[] { #if 1 //Added by Quectel { USB_DEVICE(0x05C6, 0x9090) }, /* Quectel UC15 */ { USB…

i.MX6/i.MX7 EIM总线驱动-异步通信

i.MX6/i.MX7平台,支持EIM(External Interface Module)总线扩展。在实际项目中,大部分使用该总线和FPGA通信比较多,我们这里以与FPGA为例实现该驱动。 i.MX6是使用较多的一个,我们以i.MX6为例进行分析。我手上的芯片型号是i.MX6D。 我们实现的功能是:使用EIM的16根数据线…

实习笔试准备(3)

1 第三题 1.1 题目描述 给定一个迷宫&#xff0c;找到最快从起点到达重点的路径所需要的步数。 假设迷宫如下&#xff0c;假定左上角坐标为(0, 0)&#xff0c;右下角坐标为(3, 2) 1 0 -1 1 -2 0 -1 -3 2 2 0 0 -2是迷宫的起点&#xff0c;坐标为(0, 1) -3是迷宫的终点&a…

收音机调谐拉线维修

好久没更新博客了&#xff0c;因为实在是太忙啦~刚忙完搬家的事情&#xff0c;今天正好有空&#xff0c;就给大家来点干货。 事情是这样的&#xff0c;笔者手头有一个袖珍机械调谐收音机&#xff0c;型号为德生R1012&#xff0c;FM/MW/SW1-8/TV 12Bands收音机&#xff0c;虽然是…

一台老式收音机——飞乐牌251-1(交流电子管)

飞乐牌251-1收音机 (交流电子管) 它已经在我们家里无声无息地躺了二十多年了&#xff0c;记得我最后一次去拆它是高中毕业那年&#xff0c;之后再也没有去捣鼓过。前几年老妈嫌它占地方&#xff0c;扔前问我要不要收留这个劳什子&#xff0c;我如获至宝。但是我也只是让它换了个…

44、RDA5807收音机实验

文章目录 1、特点2、控制接口3、状态转换4、实验目的5、原理图6、代码实现1、特点 RDA5807 芯片研发而成的新一代数字调频收音机模块,主要应用于 MP3/MP4 媒体播放机,具有比传统模拟制式收音机模块更突出的性能表现,音质更清晰, 噪音极少,功耗更低,集成度高,对炬力、瑞芯…