P8200 [传智杯 #4 决赛] 生活在树上easy version题目背景本题是 P8201 的简单版本两道题目的解法略有不同。本题和 P8201 在题意上的区别在于本题给定树上的边权而不是点权。小智生活在「传智国」这是一个有nnn个城市的国家各个城市由n−1n-1n−1条道路相连。每个道路都有长度wiw_iwi​我们定义小智从城市aaa走到城市bbb的代价是disa,b⨁e∈path(a,b)we\mathrm{dis}_{a, b} \bigoplus \limits_{e \in \mathrm{path}\left(a, b\right)} w_edisa,b​e∈path(a,b)⨁​we​其中⨁\bigoplus⨁表示按位异或如果你不知道什么是按位异或请参见题目下方的提示/说明path(a,b)\mathrm{path}\left(a,b\right)path(a,b)表示aaa到bbb的简单路径上的边集。也即disa,b\mathrm{dis}_{a, b}disa,b​表示将aaa与bbb的简单路径上所有边写作e1,e2,e3,…e_1, e_2, e_3, \dotse1​,e2​,e3​,…后求we1⨁we2⨁we3…w_{e_1} \bigoplus w_{e_2}\bigoplus w_{e_3} \dotswe1​​⨁we2​​⨁we3​​…的结果。有一天小智获得了去参加传智杯的机会他在前往比赛地的路上想到了一个问题但他好像不会做于是他把这个题告诉了你。聪明的同学你可以帮帮他吗题目描述小智说「由于我们的国家只有nnn个城市和n−1n-1n−1条道路那么我们的国家就相当于是一棵树。我在想在我们的国家中是否有城市满足『到城市aaa的代价和到城市bbb的代价的异或等于kkk』。好难哦我想不出来你能帮帮我吗」也就是说给定城市a,ba, ba,b和整数kkk请你计算是否存在城市ttt满足dist,a⨁dist,bk\mathrm{dis}_{t, a} \bigoplus \mathrm{dis}_{t, b} kdist,a​⨁dist,b​k。输入格式第一行有两个整数nnnmmm表示国家的城市数和询问的个数。接下来n−1n-1n−1行每行有两个整数x,y,lx, y, lx,y,l表示城市xxx与城市yyy有一条长度为lll的边。接下来mmm行每行有三个整数a,b,ka, b, ka,b,k表示小智从城市aaa走到城市bbbkkk的含义与题目描述一致。输出格式共mmm行每行一个整数。对于第iii个询问如果存在至少一个城市ttt满足要求则输出Yes。如果不存在任何一个城市满足条件则输出No。输出字符串大小写不敏感例如Yes、yES、YES、yes等都算作Yes。输入输出样例 #1输入 #15 3 1 2 2 1 3 6 2 4 8 2 5 1 1 2 4 2 3 12 1 4 10输出 #1nO No YeS输入输出样例 #2输入 #25 10 2 1 63 3 1 57 4 2 2 5 2 84 5 2 84 4 1 9977404983223574764 2 5 84 2 1 15996060349666123522 5 4 86 3 1 8428615422876116375 5 1 107 2 3 6 2 3 6 4 2 2输出 #2yeS nO YEs No YEs nO YEs yeS yeS YEs说明/提示相关概念解释「树」树是一个有nnn个结点和n−1n-1n−1条边的无向简单连通图。「按位异或」按位异或即 C、python、java 语言中的 「^」 运算。它是一个二元运算步骤是将两个数的二进制位按位比较相同为000不同为111。例如3⨁5(011)2⨁(101)2(110)263 \bigoplus 5 (011)_2 \bigoplus (101)_2 (110)_2 63⨁5(011)2​⨁(101)2​(110)2​6。请注意这是一个按位运算不是一个逻辑运算。样例 1 解释下图为传智国的地图。∀t∈{1,2,3,4,5}\forall t \in \{1, 2, 3, 4, 5\}∀t∈{1,2,3,4,5}都不可能有dist,1⨁dist,24\mathrm{dis} _{t,1} \bigoplus \mathrm{dis}_{t, 2} 4dist,1​⨁dist,2​4dist,2⨁dist,312\mathrm{dis}_{t, 2} \bigoplus \mathrm{dis}_{t, 3} 12dist,2​⨁dist,3​12于是输出No而取t5t 5t5有dist,1⨁dist,410\mathrm{dis}_{t, 1} \bigoplus \mathrm{dis}_{t, 4} 10dist,1​⨁dist,4​10于是输出Yes。数据规模与约定对于所有测试点保证1n≤5×1051 n \leq 5 \times 10^51n≤5×1051≤m≤5×1051 \leq m \leq 5 \times 10^51≤m≤5×1050≤wi2640 \leq w_i 2^{64}0≤wi​264。对于每次询问保证1≤a,b≤n1 \leq a, b \leq n1≤a,b≤n且a≠ba \neq bab0≤k2640 \leq k 2^{64}0≤k264。C实现#includearray#includevector#includeiostreamconstintmaxn1000005;intn,q;std::arraystd::vectorstd::pairint,unsignedlonglong,maxne;std::arrayunsignedlonglong,maxnb;voiddfs(constintu,constintf);intmain(){std::ios::sync_with_stdio(false);std::cin.tie(0);std::cinnq;unsignedlonglongk;for(intu,v,i1;in;i){std::cinuvk;e[u].push_back({v,k});e[v].push_back({u,k});}dfs(1,0);std::arraystd::string,2ans{nO,yEs};for(inti1,u,v;iq;i){std::cinuvk;std::coutans[(b[u]^b[v])k]\n;}}voiddfs(constintu,constintf){for(auto[v,w]:e[u])if(v!f){b[v]b[u]^w;dfs(v,u);}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容