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

翻译：

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

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

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

你从一个变量𝑥开始，它最初等于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，或者有点有相同的值即可。

代码：

1.  
   #include <iostream>
2.  
   #include <algorithm>
3.  
   #include <string.h>
4.  
   #include <string>
5.  
   #include <math.h>
6.  
   #include <stdio.h>
7.  
   #include<vector>
8.  
   #include<queue>
9.  
   #include<map>
10.  
    #include<set>
11.  
    #include<tuple>
12.  
    #include<numeric>
13.  
    #include<stack>
14.  
    using namespace::std;
15.  
    typedef long long ll;
16.  
    int n,t;
17.  
    inline __int128 read(){
18.  
    __int128 x = 0, f = 1;
19.  
    char ch = getchar();
20.  
    while(ch < '0' || ch > '9'){
21.  
    if(ch == '-')
22.  
    f = -1;
23.  
    ch = getchar();
24.  
    }
25.  
    while(ch >= '0' && ch <= '9'){
26.  
    x = x * 10 ch - '0';
27.  
    ch = getchar();
28.  
    }
29.  
    return x * f;
30.  
    }
31.  
    inline void print(__int128 x){
32.  
    if(x < 0){
33.  
    putchar('-');
34.  
    x = -x;
35.  
    }
36.  
    if(x > 9)
37.  
    print(x / 10);
38.  
    putchar(x % 10 '0');
39.  
    }
40.  
     
41.  
    int a,b;
42.  
    int x,y,z;
43.  
    map<ll,int>we;
44.  
    ll dd[100005];
45.  
    int jjk=0;
46.  
    set<ll>wee;
47.  
    vector<pair<int,int>>q[100005];
48.  
    void dfs(int x,int fa){
49.  
    if (x==b) {
50.  
    if (dd[x]==0) {
51.  
     
52.  
    jjk=1;
53.  
    }
54.  
    return;
55.  
    }
56.  
    for (int i =0; i<q[x].size(); i ) {
57.  
    if (q[x][i].first==fa) {
58.  
    continue;
59.  
    }
60.  
    dd[q[x][i].first]=dd[x]^q[x][i].second;
61.  
    if (q[x][i].first!=b) {
62.  
    we[dd[q[x][i].first]]=1;
63.  
    }
64.  
     
65.  
    dfs(q[x][i].first, x);
66.  
    }
67.  
    }
68.  
    void dfs2(int x,int fa){
69.  
    if (we[dd[x]]&&x!=b) {
70.  
    // printf("%d \n",x);
71.  
    // printf("dsa\n");
72.  
    jjk=1;
73.  
    }
74.  
    // if (dd[x]==0) {
75.  
    // jjk=1;
76.  
    // }
77.  
    for (int i =0; i<q[x].size(); i ) {
78.  
    if (q[x][i].first==fa) {
79.  
    continue;
80.  
    }
81.  
    dd[q[x][i].first]=dd[x]^q[x][i].second;
82.  
     
83.  
     
84.  
    dfs2(q[x][i].first, x);
85.  
    }
86.  
    }
87.  
    void solv(){
88.  
     
89.  
    we.clear();
90.  
     
91.  
    jjk=0;
92.  
    cin>>n>>a>>b;
93.  
     
94.  
    for (int i =0; i<=n; i ) {
95.  
    q[i].clear();
96.  
    }
97.  
    for (int i =1; i<n; i ) {
98.  
    cin>>x>>y>>z;
99.  
    q[x].push_back({y,z});
100.  
     q[y].push_back({x,z});
101.  
     }
102.  
     // if (n==2) {
103.  
     // printf("NO\n");return;
104.  
     // }
105.  
     // for (int i =1; i<=n; i ) {
106.  
     // dd[i]=0;
107.  
     // }
108.  
     //
109.  
     dd[a]=0;
110.  
     dfs(a,a);
111.  
     // for (int i =1; i<=n; i ) {
112.  
     // printf("%lld ",dd[i]);
113.  
     // }printf("\n");
114.  
     // for (int i =1; i<=n; i ) {
115.  
     // dd[i]=0;
116.  
     // }
117.  
     dd[b]=0;
118.  
     we[0]=1;
119.  
     dfs2(b, b);
120.  
     // for (int i =1; i<=n; i ) {
121.  
     // printf("%lld ",dd[i]);
122.  
     // }printf("\n");
123.  
      
124.  
     if (jjk) {
125.  
     printf("YES\n");return;
126.  
     }printf("NO\n");
127.  
     // 4
128.  
     // 4 3 2
129.  
     // 3 1 1
130.  
     // 1 4 1
131.  
     // 1 2 3
132.  
     }
133.  
     int main(){
134.  
     ios::sync_with_stdio(false);
135.  
     cin.tie(); cout.tie();
136.  
     cin>>t;
137.  
     while (t--) {
138.  
     solv();
139.  
     }
140.  
     return 0;
141.  
     }
142.  
      
143.  
      

这篇好文章是转载于：学新通技术网