2023(ICPC)江西省赛I题题解

I. Tree

题意: 两种操作，操作1:将一棵树一条路径上的边权异或上一个数，操作2:或者询问一个点周 围所有边权的异或和。

题解: 首先，异或有一个性质 A ⨁ A = 0 ⇒ A ⨁ B ⨁ A = B

在进行操作一时,对X到Y的简单路径上的每一条边权异或,会是这样的情况 X _ w1_ Z _ w2_P_w3_Y, 根据上面的性质,对w1异或一个数然后对w2异或一个同一个数,相当于对Z点相连的边权的异或和不变,只有X点和Y点的相连的异或和会被改变,所有可以先预先处理出每个节点到与它相连节点的所有边权的异或和。

进行操作一:对X点相连边的异或和异或值和对Y点相连边的异或和异或值,进行操作二:直接输出点相连的边的异或和

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define cs ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
 4 typedef long long ll; 
 5 const int N = 5e5+10;
 6  
 7 ll z[N];//z[i]表示与i点相连的边权的异或和
 8 
 9 void slove(){
10      int n,q;
11      cin >> n >> q;
12      for ( int i = 1; i < n; i++ ){
13          ll x,y,w;
14          cin >> x >> y >> w;
15          z[x] ^= w;
16          z[y] ^= w;
17      }     
18      while ( q-- ){
19          int op;
20          cin >> op;
21          if ( op == 1 ){
22             ll x,y,w;
23             cin >> x >> y >> w;        
24             z[x] ^= w;
25             z[y] ^= w;
26         }else{
27              ll x;
28              cin >> x;
29              cout << z[x] << '\n';
30         }
31      }
32 }
33 int main(){
34     cs;
35     int t;
36     t = 1;
37     while ( t-- ){
38         slove();
39     }
40     return 0;
41 }